1、算法思想

二分查找的思想很简单。假设有一个非降序的数据集合。先找出集合中最中间的那个元素，将数据集分割成两个子集。将最中间的元素和关键字key比较，如果等于key就返回，如果大于key，就证明key在前一个子集中，否则就在后一个子集查找，直到找到key返回。若没有找到返回-1。

二分查找只适用于有序数据集合，所以看到题中出现非降序、有序等字眼要想到二分查找。

2、代码实现

//区间[l.r]被划分成[l,mid]和[mid+1,r]时使用
int bsearch_1(int l.int r)
{
  while(l<r)
  {
    	int mid = l+r>>1; //右移一位代表(l+r)/2
    	if(check(mid)) r = mid; //check(mid)是判断mid是否满足 性质
    	else l = mid +1;
  }
  return l;
  
}
//区间[l.r]被划分成[l,mid-1]和[mid,r]时使用    
int bsearch_2(int l.int r)
{
	while(l<r)
	{
		int mid = l+r+1>>1;//不加1的话可能会出现死循环，比如l=r-1的情况
		if(check(mid)) l = mid;
		else r= mid-1;
	}
	return l;
}

上述两个模板使用那个要看题中如何分区间。比如给定一个题，首先写个check函数，来判断一下如果满足条件应该划到那个区间中。 **

常用模板

    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int l = 0;
        int r = nums.size()-1;
        while(l<=r)
        {    
            int mid = l+r>>1;
            if(target==nums[mid]) return mid;
            else if(target>nums[mid]) l = mid+1;
            else r = mid-1;
        }
        return -1;
    }

3、总结

二分查找的思想虽然极其简单，但是一定要注意边界问题，否则会出现查找失败、死循环等情况。