算法学习笔记-二分法
原创
一、二分查找
- 要先找到二分法的初值，low和high，比如对于一个数组==>low = 0， high = nums.size() - 1;
- 选定循环条件，可以是low <= high，也可以是low < high，选哪个需要自己进行判断，实在判断不了自己模拟一遍就行了
- 得到mid的值，mid = low + (high - low) >> 1 ，这个求中间值有多种写法，这里只是个范例。
之后就可以写出二分查找的代码了：
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的元素下标
- 查找最后一个小于等于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的数。。。？
//....这还用说嘛？三、部分题型实战
1、最大值最小化
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;
}
}2、旋转数组
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];
}
}2、山峰最高值
//直接看代码，不多说
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 删除。
评论
登录后参与评论
推荐阅读
目录