[TOC]
数组可以快速使用二分查找法的条件：
- 数组为有序数组（必须具备，否则换思路）
- 数组无重复元素（最好具备，否则查找的index无法确定是哪一个target）
一、二分查找含重复元素的数组
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;
}
};