二分查找—包括查找第一个目标元素和最后一个目标元素

学了没过多久又忘了，在这里写一下笔记。此处主要学习参考了labuladong写的二分查找笔记，也参考了别的优秀作品，加上了我自己的理解。

二分查找需要明确：

• 查找条件：找到中间的元素，还是找到多个目标元素第一个（最左边）的元素，还是多个目标元素的最后一个
• 查找区间：左闭右闭while(left<=right)，左闭右开while(left<right)。
  需要判断什么时候区间中没有元素，来作为判别条件。在while(left<=right)时，[left+1,left]区间中没有元素，退出循环。
  while(left<right)时，[left,left)中没有元素，退出循环。
  但其实左闭右开可以转换成左闭右闭。
• 什么时候返回查找到的目标元素的下标：
  • 找到中间元素：找到立即返回
  • 找边界目标元素：找到目标，不断缩小区间返回。
    • 找左边界：if(nums[mid] == target) right=mid;
    • 找右边界：if(nums[mid] == target) left=mid+1;
• 边界元素需要在循环外面打补丁：
  • 找左边界：if(left==len) return 0;目标元素比数组所有元素都大，返回-1
  • 找右边界：if(left==0) return -1;目标元素比数组所有元素都小，返回-1
• 边界目标元素的返回：
  • 左边界：当区间缩小到只有两个元素，且这两个元素相同的时候，while条件会漏掉，返回打补丁return nums[left] == target ? left : -1;
    
  • 右边界：因为找到目标元素，左边界向右缩进，left=mid+1。当while结束时，nums[left]一定不等于target，即相当于left来到了目标元素的后面一个位置，但是nums[left-1]有可能目标元素的右边界，返回打补丁return nums[left-1] == target ? (left-1) : -1;

一般查找元素

int search(vector<int>& nums, int target) {
        int len=nums.size();
        if(len == 0) return -1;
        int left=0,right=nums[len-1];//闭区间
        while(left<=right){//闭区间中不含元素的判定[left+1,left]
            int mid=left+(right-left)/2;
            if(nums[mid] == target){
                return mid;//找到元素立即返回，找左右边界元素不是找到立即返回，而是继续缩小区间
            }
            else if(nums[mid] > target){
                right=mid-1;//闭区间，从mid分割开
            }
            else if(nums[mid] < target){
                left=mid+1;
            }
        }
        return -1;//没有找到元素
    }

下面是左闭右开区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len=nums.size();
        if(len==0) return -1;
        int left=0,right=len;
        while(left < right){//左闭右开[left,right)，结束条件left=right
            int mid=left+(right-left)/2;
            if(nums[mid] == target) return mid;
            //中间值比目标值小，搜索区间[mid+1,right)
            else if(nums[mid] < target) left=mid+1;
            //中间值比目标值大，因为是右开取不到右节点，所以right更新为mid(取不到)，搜索区间[left,mid)
            else if(nums[mid] > target) right=mid;
        }
        return -1;
    }
};

下面的两个代码我写的有点问题，部分可以成功返回下标，部分返回-1
这篇博客里面的找边界目标的代码运行正确。下面的可能是我哪里细节没写对

找第一个目标元素

int left_bound(vector<int>& nums, int target){
	int len=nums.size();
	if (len == 0) return -1;
	int left=0,right=len;
	while(left < right){//因为右边界取不到索引 
		int mid=left+(right-left)/2;
		if(nums[mid]==target){
			right=mid;//缩小边界，不断向左边界靠近
		}
		else if(nums[mid]>target){
			right=mid;
		}
		else if(nums[mid]<target){
			left=mid+1;
		}
		//目标元素比数组中的所有元素都大 
		if(left==len) return -1;
		//反之区间只有两个元素时，且刚好是两个相同的元素 
		return nums[left]==target ? left : -1;
	}
}

int main(){
	vector<int> nums;
	nums.push_back(0);nums.push_back(1);nums.push_back(1);nums.push_back(2);nums.push_back(3);	
	int ans=left_bound(nums,4);
	cout<<ans<<endl;
	return 0;
} 

找最后一个目标元素

int right_bound(vector<int>& nums,int target){
	int len=nums.size();
	if l(en == 0) return -1;
	int left=0,right=len;
	while(left < right){//因为右边界取不到索引 
		int mid=left+(right-left)/2;
		if(nums[mid]==target){
			//不断向右边界靠近
			left=mid+1; 
		}
		else if(nums[mid]>target){
			right=mid;
		}
		else if(nums[mid]<target){
			left=mid+1;
		}
		//没找到右边界
		if(left==0) return -1;
		//因为找到目标，左边界向有缩进，left=mid+1。当while结束时，nums[left]一定不等于target，而nums[left-1]有可能是 
		return nums[left -1] == target ? (left-1) : -1;
	}

int main(){
vector<int> nums;
	nums.push_back(0);nums.push_back(1);nums.push_back(1);nums.push_back(2);nums.push_back(3);	
	int ans=right_bound(nums,1);
	cout<<ans<<endl;
}

参考：