1.二分查找

二分查找分为普通二分查找和二分查找变体。
普通二分查找：在一个升序，无重复元素的数组中进行查找元素
二分查找变体：数组中元素重复

1.1.普通二分查找

普通二分查找

因为数组为升序，且数组中无重复元素，所以直接使用二分法模板进行解题

public class Main {
    //左闭右开区间
    public static int findElem(int[] data, int elem) {
        int left = 0;
        int right = data.length;
        while (left < right) {
            int middle = left + ((right - left) >> 1);
            if (elem == data[middle]) {
                return middle;
            } else if (elem < data[middle]) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return -1;
    }

    //左闭右闭区间
    public static int findElem2(int[] data, int elem) {
        int left = 0;
        int right = data.length - 1;
        while (left <= right) {
            int middle = left + ((right - left) >> 1);
            if (elem < data[middle]) {
                right = middle - 1;
            } else if (elem > data[middle]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}

二分法核心就是循环不变量。
应注意以下几点：

  1. 区间是左闭右开还是左闭右闭
  2. while循环条件是否正确，即当区间为左闭右开时，left不能等于right(右边界是开区间，取不到右边界，left!=right)
  3. middle的取值，即当区间是左闭右闭时，target如果在大区间的左区间，那么原本的right = middle -1 (在判断时已经判断过target!=arr[middle],所以target在[left,middle-1]这个区间中)

——

1.2.二分查找变体