之后就可以写出二分查找的代码了:
inline int binarySearchMatrix(vector<int>& num, int target)
{
int low, high, mid; low = 0;
high = num.size() - 1; //第一步设初值,因为要找数字为target的下标,因此选择数字的长度为初值[0, num.size() - 1]
while (low <= high) //条件判断,也可以不要等于,但是要找循环外面单独判断。
{
mid = low + ((high - low) >> 1); //取中值
//之后便是喜闻乐见的那边适合去那边了
if (num[mid] == target)
{
return mid;
}
else if (num[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1; //没有找到target
}
作为一个有点逼格的算法,没有扩展怎么行,以下我总结了四个扩展,分别为:
//查找第一个与target相等的元素下标
//思路:通过上面的二分查找,假设已经找到了target,下面就是判断是不是第一个,因为序列是有序的,所以如果你用已经
//找到的target的下标mid与下标为mid - 1的数比较不就行了吗?如果nums[mid] > nums[mids - 1],那皆大欢喜,mid就是
//第一个,如果相等,那就继续适合那边去那边呗,代码如下:
inline int searchFirstEqualElement(vector<int>& num, int target)
{
int low, high, mid; low = 0; high = num.size() - 1;
while (low <= high)
{
mid = low + ((high - low) >> 1); //基本操作
if (num[mid] == target)
{
//先找到target,进行判断如果Mid =0,那必然是第一个
//如果前一个不等于mid,按照有序,那mid就是第一个。
if (mid == 0 || num[mid - 1] != target)return mid;
//如果相等,就相当于没找到,继续循环。
high = mid - 1;
}
else if (num[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1; //没有找到target
}
//查找最后一个与target相等的元素下标(不用我多说了吧)
inline int searchLastEqualElement(vector <int>& num, int target)
{
int low, high, mid; low = 0; high = num.size() - 1;
while (low <= high)
{
mid = low + ((high - low) >> 1);
if (num[mid] == target)
{
if (mid == num.size() - 1 || num[mid + 1] != target)return mid;
low = mid + 1;
}
else if (num[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1; //没有找到target
}
// 查找第一个大于等于target的元素下标
// 按照上面的分析继续,也就是说你也不一定要找到target,这个序列也不一定有target
//比如:1 2 4 6 7,target == 3; 第一个大于等于3的不就是4吗? 所以只要把上面的条件改一下就好了。
inline int searchLastGreaterElement(vector <int>& num, int target)
{
int low, high, mid; low = 0; high = num.size() - 1;
while (low <= high)
{
mid = low + ((high - low) >> 1);
//只要大于等于target都行,即:num[mid] >= target, num[mid - 1]却小于,mid就是第一个大于等于target的数
if (num[mid] >= target)
{
if (mid == 0 || num[mid - 1] < target)
return mid;
high = mid - 1;
}else{
low = mid + 1;
}
}
return -1; //没有找到target
}
//查找最后一个小于等于target的元素下标(不用多说了)
inline int searchLastWeakerElement(vector <int>& num, int target)
{
int low, high, mid; low = 0; high = num.size() - 1;
while (low <= high)
{
mid = low + ((high - low) >> 1);
if (num[mid] <= target)
{
if (mid == num.size() - 1 || num[mid + 1] > target)
return mid;
low = mid + 1;
}else{
high = mid - 1;
}
}
return -1; //没有找到target
}
//为什么没有查找最后一个大于等于target的数,为什么没有查找第一个小于等于target的数。。。?
//....这还用说嘛?
leetcode875爱吃香蕉的珂珂https://leetcode-cn.com/problems/koko-eating-bananas/
//分析:
//(1)只要吃完一堆,那这一个小时都不能再去吃别的,也就是说,,最少需要的时间为香蕉的堆数
// 也就是吃的个数为这么多堆中最大的一个,比如:[3, 6, 7, 11],你每次吃11个,四个小时就可以吃完
//(2)最小肯定是吃一根
//(3)现在给一个时间,规定在这时间内最小吃多少能吃完,也就是说在[1, max(nums)]选一个数出来,能够在h小时内吃完,
//并且吃的个数最小
//这是典型的查找第一个大于等于的元素,比如[1, 7],我在速度为6个的时候吃完了(时间小于h)
//在速度为5的时候吃不完,时间大于h,那最小不就是6吗?因此代码如下:
namespace lt875 {
int maxNum(vector <int>& piles)
{
int num = -1;
for (auto& elem : piles)
{
if (elem > num)
{
num = elem;
}
}
return num;
}
bool isOk(int mid, vector<int>& piles, int h)
{
int h1 = 0;
for (auto& elem : piles)
{
h1 += static_cast<int>(ceil(elem * 1.0 / mid));
}
return h1 <= h;
}
//从1~max里找第一个能在规定的小时里面的吃完的数目
int minEatingSpeed(vector<int>& piles, int h)
{
int high = maxNum(piles);
int low = 1, mid; //(1)找low和high
while (low <= high)//(2)条件
{
mid = low + ((high - low) >> 1); //(3)中值
//cout << mid << endl;
if (isOk(mid, piles, h))
{
if (mid == 1 || !isOk(mid - 1, piles, h))
{
return mid;
}else{
high = mid - 1;
}
}
else
{
low = mid + 1;
}
}
return -1;
}
}
建议做一下以下题锻炼一下:
leetcode1011在 D 天内送达包裹的能力https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
leetcode410分割数组的最大值https://leetcode-cn.com/problems/split-array-largest-sum/
leetcode1283 使结果不超过阈值的最小除数https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold/
代码我也给出:
namespace lt1011 {
int maxNum(vector <int>& piles)
{
int num = -1;
for (auto& elem : piles)
{
if (elem > num)
{
num = elem;
}
}
return num;
}
int maxSum(vector <int>& weights)
{
int sum = 0;
for (auto& elem : weights)
{
sum += elem;
}
return sum;
}
bool isOk(int mid, vector <int>& weights, int D)
{
int d = 0, sum = 0;
for (auto& elem : weights)
{
sum += elem;
if (sum > mid)
{
sum = elem;
d ++;
}
}
d ++;
return d <= D;
}
int shipWithinDays(vector<int>& weights, int D)
{
int low = maxNum(weights), mid;
int high = maxSum(weights);
while (low <= high)
{
mid = low + ((high - low) >> 1);
if (isOk(mid, weights, D))
{
if (mid == maxNum((weights)) || !isOk(mid - 1, weights, D))
{
return mid;
}
else
{
high = mid - 1;
}
}
else
{
low = mid + 1;
}
}
return -1;
}
}
//................................
namespace lt410 {
int maxNum(vector <int>& piles)
{
int num = -1;
for (auto& elem : piles)
{
if (elem > num)
{
num = elem;
}
}
return num;
}
int maxSum(vector <int>& weights)
{
int sum = 0;
for (auto& elem : weights)
{
sum += elem;
}
return sum;
}
bool isOk(int mid, vector <int>& weights, int D)
{
int d = 0, sum = 0;
for (auto& elem : weights)
{
sum += elem;
if (sum > mid)
{
sum = elem;
d ++;
}
}
d ++;
return d <= D;
}
int splitArray(vector<int>& nums, int D)
{
int low = maxNum(nums), mid;
int high = maxSum(nums);
while (low <= high)
{
mid = low + ((high - low) >> 1);
if (isOk(mid, nums, D))
{
if (mid == maxNum((nums)) || !isOk(mid - 1, nums, D))
{
return mid;
}
else
{
high = mid - 1;
}
}
else
{
low = mid + 1;
}
}
return -1;
}
}
//.............................
namespace lt1283 {
int maxNum(vector <int>& piles)
{
int num = -1;
for (auto& elem : piles)
{
if (elem > num)
{
num = elem;
}
}
return num;
}
bool isOk(int mid, vector<int>& piles, int h)
{
int h1 = 0;
for (auto& elem : piles)
{
h1 += static_cast<int>(ceil(elem * 1.0 / mid));
}
return h1 <= h;
}
int smallestDivisor(vector<int>& nums, int threshold)
{
int low = 1, high = maxNum(nums), mid;
while (low <= high)
{
mid = low + ((high - low) >> 1);
if (isOk(mid, nums, threshold))
{
if (mid == 1 || !isOk(mid - 1, nums, threshold))
return mid;
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
}
https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
即:[0 1 2 3 4 5 6 7 8] ==>在下标为五处旋转,变为==》 [5 6 7 8 0 1 2 3 4 ]
就是在这这样一个数组上面找target;这个其实有规律的:
//分析:
//(1)可以把数组分为大段和小段,5~8为大段, 0~4为小段:
//(2)对于mid, 如果nums[mid] >= nums[low] ,nums[mid] > nums[high],那mid必在大段
//(3)对于mid, 如果nums[mid] < nums[low] ,nums[mid] <= nums[high],那mid必在小段
//对于有相等元素的序列,比如2 2 1 2 2无法判断大小段,所以另外考虑
//开始分段,,nums[mid] > nums[low]虽然无法确定是小段还是大段,但可以肯定的是,[low, mid)肯定是有序的
//所以如果target在[low, mid)之间那可以直接使用二分查找,如果不在那比如是在mid和high之间,只需要把low = mid + 1、、
//然后再进入循环即可
//nums[mid] < nums[high]一样分析。
namespace lt81 {
bool search(vector<int>& nums, int target)
{
int len = static_cast<int>(nums.size());
if (len == 0)return false;
int low = 0, high = len - 1, mid;
while (low <= high) {
mid = low + ((high - low) >> 1);
if (nums[mid] == target)return true;
else if (nums[mid] > nums[low]){
if (nums[low] <= target && target < nums[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}else if (nums[mid] < nums[high]){
if (nums[mid] < target && target <= nums[high]){
low = mid + 1;
}else{
high = mid - 1;
}
}else{
if (nums[mid] == nums[low]) low ++;
if (nums[mid] == nums[high]) high --;
}
}
//2 1 2 2 2 1 //1 2 2
return false;
}
}
可以锻炼一下33题https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
//寻找循环数组里的最小值
//单纯的最小值,直接找low下标对应的值就好了。。。不过要满足几个条件
//(1)[low, high]是有序的,所以我们目标就是把low,high变成有序
//看mid, 如果nums[mid] >= nums[low]那么要么在大段,要么low,high是有序的,,,所以代码如下
namespace lt153 {
int findMin(vector<int>& nums)
{
//3 4 5 1 2
int low = 0, high = nums.size() - 1, mid;
while (low < high)
{
if (nums[low] < nums[high])
{
return nums[low];
}
mid = low + ((high - low) >> 1);
if (nums[mid] >= nums[low])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return nums[low];
}
}
//如果存在相同的数字
namespace lt154 {
int findMin(vector<int>& nums)
{
//10 1 10 10 10
int low = 0, high = nums.size() - 1, mid;
while (low < high)
{
if (nums[low] < nums[high])
{
return nums[low];
}
mid = low + ((high - low) >> 1);
if (nums[mid] > nums[low])
{
low = mid + 1;
}else if (nums[mid] == nums[low])
low++;
else
{
high = mid;
}
}
return nums[low];
}
}
//直接看代码,不多说
namespace lt852 {
int peakIndexInMountainArray(vector<int>& arr)
{
int low = 0, high = arr.size() - 1, mid;
while (low < high) {
mid = low + ((high - low) >> 1);
if (arr[mid] > arr[mid + 1])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
//24,69,100,99,79,78,67,36,26,19
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。