数组可以快速使用二分查找法的条件：
- 数组为有序数组（必须具备，否则换思路）
- 数组无重复元素（最好具备，否则查找的index无法确定是哪一个target）
一、二分查找无重复元素数组
704. 二分查找（简单难度）
class Solution {
public:
// 定义target在区间[left,right]
int search1(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while (left <= right) {
int mid = left + ((right-left) / 2);//等价于(left + right)/2，防止溢出
if(nums[mid]==target) return mid;
else if(nums[mid]>target) right = mid - 1;
else left = mid + 1;
}
return -1;
}
// 定义target在区间[left,right)
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int mid = left + ((right-left) / 2);//等价于(left + right)/2，防止溢出
if(nums[mid]==target) return mid;
else if(nums[mid]>target) right = mid;
else left = mid + 1;
}
return -1;
}
};
35. 搜索插入位置
// 定义target在区间[left,right)
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int mid = left + ((right-left) / 2);//等价于(left + right)/2，防止溢出
if(nums[mid]==target) return mid;
else if(nums[mid]>target) right = mid;
else left = mid + 1;
}
return -1;
}
二、二分查找算数平方根
69. x 的平方根
class Solution {
public:
/* 本题是求解x的算数平方根，难点在于不准使用内置函数和运算符。
思路：二分查找+除法比较
x的算数平方根的范围只能是[1,x],只能遍历查找哪一个是平方根
这是一个有序数组，显然二分查找更加快捷
这道题注意，不能使用mid*mid和x比较，因为x的数值比较大，容易溢出，可以x/mid和mid比较*/
int mySqrt(int x) {
int left=1;
int right=x;
while(left<=right){
int mid=left+(right-left)/2;
if(x/mid==mid) return mid;
else if(x/mid<mid)right=mid-1;
else left=mid+1;
}
return right;
}
};
367. 有效的完全平方数
class Solution {
public:
/*解析：本题的题意是判断一个数是否是完全平方数
难点在于输入的num的范围非常大。
显然一个完全平方数必须可以被某个数整除，即在[1,num]间是否存在一个数可以被num整除
由于num非常大，所以查找必须更加快捷，只能用二分查找法。
当一个数满足num/i==i&&num%i==0时才是完全平方数，
注意num/i==i不能保证num就是完全平方数，因为num/i可能会舍弃小数
*/
bool isPerfectSquare(int num) {
int left=1;
int right=num;
while(left<=right){
int mid=left+(right-left)/2;
// 三种情况，注意相等的判断条件
if(num%mid==0&&num/mid==mid) return true;
else if(num/mid>mid) left=mid+1;
else right=mid-1;
}
return false;
}
};
三、二分查找含重复元素的数组
34. 在排序数组中查找元素的第一个和最后一个位置（中等难度）
class Solution {
public:
/*解析：本题是在一个排序数组中查找，首选二分查找法。
本题的难点在于数组中存在重复元素，传统的二分查找法可以找到其中某一个target，但不能判断是哪一个
可以巧妙地在传统二分查找得到的index上试着左移或右移来找到边界。
*/
vector<int> searchRange(vector<int>& nums, int target) {
int index=binarySearch(nums,target);//尝试二分查找
if(index==-1) return {-1, -1};// 数组中不存在target
// 此时数组中存在target，但是不确定有几个target，index指向其中的一个target
// 寻找左边界，尝试多次移动左边界
int leftBorder=index;
while(leftBorder-1>=0&&nums[leftBorder-1]==target)leftBorder--;
// 寻找右边界，尝试多次移动右边界
int rightBorder=index;
while(rightBorder+1<nums.size()&&nums[rightBorder+1]==target)rightBorder++;
return {leftBorder, rightBorder};
}
private:
// 二分查找函数[left,right]
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
int res = nums.size(); // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int mid = left + ((right - left) / 2);//等价于(left + right)/2，防止溢出
if(nums[mid]==target) return mid;
if(nums[mid]>target) right = mid - 1;
else left = mid + 1;
}
return -1;
}
};
剑指 Offer 53 - I. 在排序数组中查找数字 I（简单难度）
class Solution {
public:
/*解析：本题是在一个排序数组中查找，首选二分查找法。
本题的难点在于数组中存在重复元素，传统的二分查找法可以找到其中某一个target，但不能判断是哪一个
可以巧妙地在传统二分查找得到的index上试着左移或右移来找到边界。
*/
int search(vector<int>& nums, int target) {
int index=binarySearch(nums,target);//尝试二分查找
if(index==-1) return 0;// 数组中不存在target
// 此时数组中存在target，但是不确定有几个target，index指向其中的一个target
// 寻找左边界，尝试多次移动左边界
int leftBorder=index;
while(leftBorder-1>=0&&nums[leftBorder-1]==target)leftBorder--;
// 寻找右边界，尝试多次移动右边界
int rightBorder=index;
while(rightBorder+1<nums.size()&&nums[rightBorder+1]==target)rightBorder++;
return rightBorder-leftBorder+1;
}
// 二分查找函数[left,right]
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
int res = nums.size(); // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int mid = left + ((right - left) / 2);//等价于(left + right)/2，防止溢出
if(nums[mid]==target) return mid;
if(nums[mid]>target) right = mid - 1;
else left = mid + 1;
}
return -1;
}
};
四、二分查找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值（中等难度）
154. 寻找旋转排序数组中的最小值 II（困难难度）
剑指 Offer 11. 旋转数组的最小数字（简单难度）
class Solution {
public:
/*本题是求一个有重复元素的旋转排序数组中的最小值，
实际上无论是否旋转，数组的最小值都是不变的，所以通过这道题很简单。
由于限定算法的时间复杂度为O(logn)，所以必须使用二分查找法。
假设数组最后1个元素为nums[right]，
则最小值的右侧元素都<=nums[right];最小值的左侧元素都>=nums[right];
我们的nums[mid]可以和nums[right]比较来进行二分查找
有没有重复元素会影响nums[mid]==nums[right]的情况：
没有重复元素时，mid一定就是right，right==mid即可，当然right-=1也对。
有重复元素时，mid可能在最小值右侧或者左侧，索性采取保守策略，right统一左移1个元素。
*/
int findMin(vector<int>& nums) {
int left = 0;// 左指针
int right = nums.size() - 1;//右指针
// 循环遍历[left,right]
while (left < right) {
int mid = left + (right - left) / 2;//折半操作
// 如果nums[mid]==nums[right]，说明mid就是右指针，右指针左移1次
if(nums[mid]==nums[right]) right -= 1;//无重复元素时right = mid也可以
// 如果nums[mid]<nums[right],说明mid在最小值右侧，移动右指针
else if (nums[mid] < nums[right]) right = mid;
// 如果nums[mid]>nums[right],说明mid在最小值左侧，移动左指针
else left = mid + 1;
}
// 遍历结束时，left==right，指向同一个元素，就是最小值
return nums[left];
}
};
五、二分查找旋转排序数组中的某个值
33. 搜索旋转排序数组（中等难度）
class Solution {
public:
/* 本题的题意中提到了排序以及时间复杂度为O(log n)，所以在暗示你使用二分查找法。
本题是在一个局部有序的数组中查找某个值，原先升序数组经过旋转变成了局部有序，增加了复杂度
本题的旋转数组有两个升序区间。
二分查找法最重要的明白nums[mid]和谁比较，本题整体是nums[mid]和target比较，存在三种情况：
nums[mid]和nums[0]的比较结果会影响上述三种情况的判断。*/
int search(vector<int>& nums, int target) {
int n = nums.size();
if (n==0) return -1;
if (n==1) return nums[0] == target ? 0 : -1;
int left = 0;// 左指针
int right = n - 1;// 右指针
// 二分查找[left,right]
while (left <= right) {
int mid = right+(left-right) / 2;
// 如果nums[mid] == target，已找到，直接返回
if (nums[mid] == target) return mid;
// 如果nums[mid] >=nums[0]，说明mid在第一段升序区间中，直接返回
if ( nums[mid]>=nums[0] ) {
if (nums[0] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
// 如果nums[mid] <nums[0]，说明mid在第二段升序区间中，
else {
// 如果nums[mid]< target并且target没有越界，移动左指针
if (nums[mid] < target && target <= nums[n - 1]) left = mid + 1;
// 如果nums[mid]>= target，移动右指针
else right = mid - 1;
}
}
return -1;
}
};
81. 搜索旋转排序数组 II（中等难度）
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size();
if (n==0) return false;
if (n==1) return nums[0] == target;
int left = 0;// 左指针
int right = n - 1;// 右指针
// 二分查找[left,right]
while (left <= right) {
int mid = right+(left-right) / 2;
// 如果nums[mid] == target，已找到，直接返回
if (nums[mid] == target) return true;
if(nums[left] == nums[mid] && nums[mid] == nums[right]){
left++;
right--;
}
// 如果nums[mid] >=nums[0]，说明mid在第一段升序区间中，直接返回
else if ( nums[mid]>=nums[left] ) {
if (nums[left] <=target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
// 如果nums[mid] <nums[0]，说明mid在第二段升序区间中，
else {
// 如果nums[mid]< target并且target没有越界，移动左指针
if (nums[mid] < target && target <= nums[n - 1]) left = mid + 1;
// 如果nums[mid]>= target，移动右指针
else right = mid - 1;
}
}
return false;
}
};
面试题 10.03. 搜索旋转数组
class Solution {
public:
/*该题的难点在于首尾可能存在相同的数，从而不具备二段性*/
int search1(vector<int>& arr, int target) {
int left=0, right=arr.size()-1;
// 恢复二段性
while(right!=0 && arr[0]==arr[right]) right--;
//找到旋转点
while(left<right){
int mid=(left+right+1)/2;
if(arr[mid]>=arr[0]) left=mid;
else right=mid-1;
}
//确定搜索片段
if(target>=arr[0]){
left=0;
right=right;
}
else{
left++;
right=arr.size()-1;
}
//二分搜索
while(left<=right){
int mid=(left+right)/2;
if(target==arr[mid]){
//找到最左边的点
if(mid>0){
if(arr[mid-1]!=target){
return mid;
}
else{
right=mid-1;
continue;
}
}
else return mid;
}
else if(target<arr[mid])right=mid-1;
else left=mid+1;
}
return -1;
}
};
六、有序数组中的单一元素
540. 有序数组中的单一元素
class Solution {
public:
/*该题可以利用索引的奇偶性来进行二分查找，假设目标索引是x
对于下标x左边的下标y，如果nums[y]=nums[y+1]，则y一定是偶数；
对于下标x右边的下标z，如果nums[z]=nums[z+1]，则z一定是奇数。
下标x是相同元素的开始下标的奇偶性的分界*/
int singleNonDuplicate(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int mid = left+(right-left)/2;
// 查找区间只剩一个元素，就是答案
if(left==right) return nums[mid];
// 如果索引是奇数
mid-=mid&1;//如果是奇数，mid&1=1
if(nums[mid]==nums[mid+1]) left=mid+2;
else right = mid;
}
return -1;
}
};
七、按值二分
287. 寻找重复数
class Solution {
public:
/*cnt[i]表示nums数组中<=i的个数,比如:
[1,2,3,4,4,5,6,7] nums
[0,1,2,3,4,5,6,7] 下标
[0,1,2,3,5,6,7,8] cnt[i]
观察cnt[i]和下标的值得出结论:
当 i < target 时,cnt[i]=i
当 i >= target 时,cnt[i]>i*/
int findDuplicate(vector<int>& nums) {
int n = nums.size();
int left=1, right = n-1, res = -1;
// 二分查找[left,right]
while (left<=right) {
int mid = right+(left-right)/2;
// 遍历整个数组
int cnt = 0;//数组中小于等于mid的个数
for (int i=0;i<n;++i) {
if(nums[i]<=mid) cnt++;
}
if(cnt<=mid)left=mid+1;
else {
right = mid-1;
res = mid;
}
}
return res;
}
};
4. 寻找两个正序数组的中位数（困难难度）
class Solution {
public:
/*中位数是有序数组中可以把所有元素左右等分的一个元素，
如果数组元素是奇数个，正好是中间位置的元素；
如果数组元素是偶数个，则是中间2个元素的均值；
一个自然的思路是：合并两个有序数组为一个有序数组，然后通过有序数组的下标计算中间位置
该算法的思路是O(m+n)*/
double findMedianSortedArrays1(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size();
int n=nums2.size();
int len=m+n;
vector<int> res(len);
int i=0,j=0,k=0;
while(i<m&&j<n){
if(nums1[i]<=nums2[j]) res[k++]=nums1[i++];
else res[k++]=nums2[j++];
}
while(i<m) res[k++]=nums1[i++];
while(j<n) res[k++]=nums2[j++];
// 一种统一处理中位数的技巧
int left=(len+1)/2;
int right=(len+2)/2;
// 从两个有序数组中查找第left大和第right大的数
double mean=(res[left-1]+res[right-1])/2.0;
return mean;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
// 想要寻找的位置
int left=(m+n+1)/2;
int right=(m+n+2)/2;
// 从两个有序数组中查找第left大和第right大的数
double mean=(findKth(nums1,nums2,0,0,left)+findKth(nums1,nums2,0,0, right))/2.0;
return mean;
}
// 从nums1的[i:]和nums2[j:]的两个有序区间中查找第k大的数
int findKth(vector<int>& nums1, vector<int>& nums2,int i, int j, int k){
// 终止条件
if(i>=nums1.size()) return nums2[j+k-1];//nums1为空数组,直接从nums2中找
if(j>=nums2.size()) return nums1[i+k-1];//nums2为空数组,直接从nums1中找
if(k==1) return min(nums1[i], nums2[j]);// 查找第1个元素，直接返回
// 查找nums1中的第k/2大元素，不存在则设为无穷大
int midVal1=(i+k/2-1<nums1.size())? nums1[i+k/2-1] : INT_MAX;
// 查找nums2中的第k/2大元素，不存在则设为无穷大
int midVal2=(j+k/2-1<nums2.size())? nums2[j+k/2-1] : INT_MAX;
// 如果midVal1<midVal2，说明中位数肯定不在nums1的前k/2个数
if(midVal1<midVal2) return findKth(nums1, nums2, i+k/2,j, k-k/2);
// 如果midVal1>=midVal2，说明中位数肯定不在nums2的前k/2个数
else return findKth(nums1, nums2, i,j+k/2 , k-k/2);
}
};