此系列是我用kotlin二刷leetcode写的总结，会总结用各个方法做的题目以及心得，主要是剑指offer专栏的题目

首先总结下二分查找几个模板

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

二分查找

第一题剑指offer11
和模板的不同：

• while循环中，每次想判定往那个方向走，必须让nums[mid]和nums[high]比较，为了让nums[high]有效，high的初值需要设定为nums.length-1。
• 此外，需要明确题解二分的写法是左闭右闭的，那么一般我们写二分的时候，左闭右闭的情况下，循环条件一般为low<=high，这里为什么又变成了low<high?
  因为一般二分时，low==high时，答案还不确定，还需在进行一次判定，而该题在low==high时，答案确定，必然是low(或者high)，因此循环条件为low<high。

 fun minArray(numbers: IntArray): Int {
        var left=0
        var right=numbers.size-1
        while (left<right){
            val mid=left+(right-left)/2
            val value=numbers[mid]
            //和numbers[right]比较的原因是寻找递增的一边，因为最小值肯定在非递增和递增的分界点或者开头处
            if (value>numbers[right])left=mid+1
            else if (value<numbers[right])right=mid
            //相等时说明mid和right中间要么一直等，要么right处于一个单独的连续块。此时要right退出连续块才能继续查找，因为连续不能
            //证明递增性
            else if(value==numbers[right])right--
        }
        return numbers[left]
    }