二分查找总结

使用条件：

线性表是有序表

二分查找要求数据结构必须是顺序表，也就是类似于数组的连续存储，因为只有这样才能一下定位出数组的中间位置（直接使用类似a[len / 2]），然后就可以把数组一分为二，进行后面的操作。 但是对于链表，由于存储是离散的，不能像数组一样，快速定位中间位置，来把链表一分为二，所以一般的二分查找不能直接应用于链表

基础版

左闭右闭

int binary_search(vector<int> nums, int target) {
	int start=0, end=nums.size()-1; //注意end
	while(start <= end) {	//注意循环条件
		int mid = start+(end-start)/2;	//计算中间下标
    	if(nums[mid] == target) 	//如果找到了，就返回下标
        	return mid;
    	if(nums[mid] < target) start=mid+1;	//如果发现这个数比目标数字小，就说明左半边都没有，直接从mid+1开始
    	else end=mid-1;	//如果发现这个数比目标数字大，就说明右半边都没有，直接从mid-1开始
	}
}

左闭右开

int binary_search(vector<int> nums,int target) {
	int start=0, end=nums.size(); //注意end
	while(start < end) {	//注意循环条件
		int mid = start+(end-start)/2;	//计算中间下标
    	if(nums[mid] == target) 	//如果找到了，就返回下标
        	return mid;
    	if(nums[mid] < target) start=mid+1;	//如果发现这个数比目标数字小，
            //就说明左半边都没有，直接从mid+1开始
    	else end=mid;	//因为右边界取不到，所有不需要减一
	}
}

升级版（可以有重复值)

当数组中有重复值的时候,返回该值第一个出现或者最后一个出现的下标. 比如[1,2,2,2,2,2,3],如果返回第一个出现的地方,应该返回1,如果返回最后一个,应该返回5. 首先我们可以想到,可以通过二分法拿到某一个目标值,然后向左或者向右遍历找到边界 适用于： 一个就是很直接让你查找目标值的最左或者最右,另一个就是需要你查出目标值的区间起始下标.

最左值

//缩小左区间求左边界
int binary_search_L(vector<int> nums, int target) {
    int left = 0, right = nums.size();
    while(left<right) {
        int mid = left + (right - left)/2;
        if(nums[mid] < target)
            left = mid + 1;
        else right = mid;	//相等时让右边界为目标值，继续缩小左区间[left,mid)
        if(left == nums.size() || nums[left] != target)
            return -1; 
        return left;
    }
}

//F2
class Solution {
public:
    int search(vector<int>& nums, int target) {
       int left = 0, right = nums.size()-1;
        while(left<=right) {
        int mid = left + (right - left)/2;
        if(target > nums[mid])
            left = mid + 1;
        else right = mid-1;	//相等时让右边界为目标值，继续缩小左区间[left,mid)
        }
        if(left == nums.size() || nums[left] != target)
            return -1; 
        return left;
    }
};

为什么该算法能够搜索左侧边界？ 关键在对于 nums[mid]==target 这种情况的处理，找到 target 时不要立即返回，而是缩小搜索区间的上界 right ，在区间 [left,mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

最右值

//向右逼近右边界 F1 左闭右开
int binary_search_R(vector<int> nums, int target) {
    int left = 0, right = nums.size();
    while(left<right) {
        int mid = left + (right - left)/2+1;
        if(target < nums[mid])
            right = mid;
        else left = mid + 1;
    if(0 right||) return -1;
    
    return right - 1;//或返回left[mid,right)
    }
}

//F2 左闭右闭
int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            auto mid = left + (right - left)/2;
            if(target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        }
        if(right < 0 || nums[right] != target)
            return -1;
        return right;
}