二分查找法

开始算法的简单学习，今天先从二分查找法开始

二分查找

代码实现：

int binary_search(int start,int end,int key){int ret = -1;int mid;while (start <= end){mid = start + ((end - start) >> 1);if(arr[mid] < key)start = mid + 1;else if(arr[mid] > key)end = mid - 1;else{ret = mid;break;}}return ret;
}

这个是常用的二分法的代码实现，但是在这里我们仍然有很多要注意的地方：

while的循环条件与start end更新

有时候会疑惑循环不变量中我们什么时候使用<或<=。而在start和end的更新中不知道什么时候使用+1或-1或不变。我们需要理解什么情况下怎么去使用。

当有序数组的数据呈闭区间的时候，即[start,end]。我们令：

while(start <= end)     //当我们考虑start=end时，条件必须成立，所以等于关系也是其中的一种情况
...
start = mid + 1     //由于每一次的比较中，先前mid的值经过了一次比较，所以需要+1-1来避免重复比较
...
end = mid - 1

当有序数组存在开区间时，如[) (] ()，实际上它们都隐含了一个信息——start!=end，否则区间是不成立的，因此：

while(start < end)  //当start=end时，搜索区间实际上是不成立的
...
start = ？？？ //这个和左右的开闭性相关，要考虑什么时候该包括，什么时候不该包括，应该明确有效的搜索区间的范围是什么
end = ？？？

二分法解题思路

我们刚刚实现的是bsearch，即二分查找匹配的数值，实际上更多时候我们需要查找的是一个区间，即在数组内查找第一个不小于X的数值的下标：

int lower_bound(vector<int> arr, int target){left = 0;right = arr.size() - 1;while (left <= right){int mid = left + (right-left)>>1;if (arr[mid] < target)left = mid + 1;else:right = mid -1;}return left;
}

现在，如果程序要求我们返回数组中一个=\>\>=\<\<=某个数的起始下标，实际上可以根据数组的有序性，将他们联系起来：

• >= 这个是最基本的我们binary_search的返回值X就是它的左边界，得到答案 X

• > 我们可以把这个问题的转换成，>= x+1 ，得到答案X+1

• < 实际上就是>=问题的补集，得到答案(>=x) - 1

• <= 是>问题的补集，我们可以得到答案 （>x）-1

以后遇到这种问题，都可以通过这种转换的思想来实现

练习：

704. 二分查找

class Solution {
public:int search(vector<int>& nums, int target) {int start = 0;int end = nums.size()-1;
​while (start <= end){int mid = end + (start-end)/2;  //这里的除法我一开始使用了位运算，但是由于这里会涉及到有符号整数的运算，所以不能使用位运算int num = nums[mid];if(target > num)start = mid + 1;else if (target < num)end = mid - 1;else {return mid;}}return -1;}
};

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = lower_bound(nums,target);if(nums.empty() || left == nums.size() || nums[left]!=target ){//当left==len(nums)时，说明数组中没有>=target的数return vector<int>{-1,-1};}int right = lower_bound(nums,target+1)-1;return vector<int>{left,right};
​}//返回>=target的第一个数int lower_bound(vector<int>& nums,int target){int start = 0;int end = nums.size() - 1;while (start <= end){int mid = (end - start)/2 + start;if(nums[mid] < target){start = mid + 1;}else{end = mid -1;}}return start;}
};

441. 排列硬币

class Solution {
public:int arrangeCoins(int n) {if(n==1) return 1;int start = 1;int end = n;while (start <= end){long mid = start + ((end - start)>>1);if (mid*(mid+1)/2 <= n) //更新比较条件start = mid +1;elseend = mid-1;}return start-1;     //由于得到的是大于n的阶层数，所以想要得到能完整标识的阶层数要-1}
};

367. 有效的完全平方数

class Solution {
public:bool isPerfectSquare(int num) {int start = 1;int end = num;while(start <= end){long mid = start + ((end -start)>>1);if(mid*mid==num){return true;}else if(mid*mid >num){end = mid-1;}else{start = mid +1;}}return false;}
};