二分查找板子

二分查找實際上就是採用了分治法的思想

以下模板都以升序數組為準

模板一: 標準的二分查找

場景：數組元素有序且不重覆

有的話返回索引，沒有返回-1

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {//<=指可以取到右區間，是[left,right]
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] > target) right = mid - 1;//證明target可能在mid左側
        else left = mid + 1;//證明nums[mid] < target, target可能在mid右側
    }
    
    return -1;
}

模板二：二分查找找邊界

二分查找左/有邊界是二分查找的變式，一般有如下場景：

1）第一種情況

• 數組總體有序，包含重覆元素
• 數組部分有序，且不包含重覆元素

2）第二種情況

• 數組部分有序，且包含重覆元素

二分查找找左邊界

1）針對第一種情況：

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {//這是左閉右開[,)，不包含最後一個數，left = right 的時候會跳出
        int mid = left + ((right - left) >> 1);
        if (nums[mid] < targrt) left = mid + 1;
        else right = mid;//nums[mid] >= target, 都需要往左邊收縮邊界（主要）
    }
    //因為裡面是沒有判斷left = right 這個索引的位置，需要打個補丁
    return nums[left] == target ? left : -1;
}

2）針對第二種情況（模板有誤）

二分查找找右邊界

1）針對第一種情況

int binarySearch(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {
        mid = left + ((right - left) >> 1) + 1;//需要註意，這裡多加了個1，這樣無論是奇偶數，中間位置都偏右，這樣避免了死迴圈（如果不加1，比如{2，2}就會死迴圈
        if (nums[mid] > target) right = mid - 1;//收縮右邊界
        else left = mid;//numd[mid] <= target,都需要收縮左邊界（主要）
    }
    //打個補丁,這裡寫左右都可以
    return nums[left] == target ? left : -1;
}

2)針對第二種情況

二分查找找左右邊界

分別查找左右邊界即可

1）第一種情況

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res{-1,-1};//res[0]存左邊界，res[1]存右邊界
    
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {//先找左邊邊界
        mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left  = mid + 1;
        else right = mid;
    }
    res[0] = nums[left] == target ? left : -1;
    
    if (res[0] != -1) {//存在左邊邊界查找右邊邊界
        if (left == nums.size() - 1 || nums[left + 1] != target) {//可能只有一個target,它的位置可能在末尾/其他位置
            res[1] = left;
        }
        else {//有多個target
            right = nums.size() - 1;
            
            while (left < right) {
                mid = left + ((right - left) >> 1) + 1;
                if (nums[mid] > target) right = mid - 1;
                else left = mid;
            }
            res[1] = nums[left] == target ? left : -1;
        }
    }
    
    return res;
}

模板三：二分查找找極值點

二分查找的一種變式：找極值，即是v或者^的最值點；

我們查找的時候不再是和target進行比較，而是和相鄰元素比較，以達到某種單調區間檢測的效果

下麵以查找^的極值點寫一個模板：

int binarySearch(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left <= right) {
       mid = left + ((right - left) >> 1);
       
        if (nums[mid] > nums[mid] + 1 && nums[mid] > nums[mid - 1]) return mid;
        else if (nums[mid] > nums[mid + 1]) right = mid - 1;//極值點在左邊
        else left = mid + 1;//極值點在右邊
    }
    
    return -1;
}