算法（九）--二分查找

二分查找

重要重要！二分查找的前提是有序数组！并且元素不能重复，如果重复查找返回的下标可能不是唯一的。

循环不变量原则：根据定义不变量区间来判断while循环条件语句以及循环体内的操作。区间分为两种：左闭右闭区间和左闭右开区间。左闭右闭区间的循环条件是left<=right，左闭右开区间的循环条件是left<right。在循环中一定要根据区间的定义来确定边界条件，进行边界处理

二分查找的基本模板

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while(left<=right) {
            int mid = (right+left)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] > target) {
                right = mid - 1;
            }
            else left = mid + 1;
        }
        return -1;
    }
};

找到第一个大于等于target的元素的位置

// 找到第一个大于等于target的元素的位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = (left+right)/2;
            if (nums[mid] >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

二段有序数组的查找

不能在通过target值与nums[mid]的大小关系来判断target在左段还是右段，因为这样会导致无法判断左段和右段的有序性。应该先判断mid左段和右段的有序性，在判断target在不在有序的一段中，根据这个来进行left和right的更新

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while(left<=right) {
            int mid = (right+left)/2;
            if(nums[mid] == target) return mid;
            if(nums[left] < nums[mid]) {
                // 左边为有序区间
                (target >= nums[left] && target < nums[mid]) ? right = mid-1 : left = mid + 1;
            }
            else {
           (target > nums[mid] && target <= nums[right]) ? left = mid + 1 : right = mid - 1;
            }
        }
        return -1;
    }
};