二分查找算法

前提：有序数组

1. 首先确定整个查找区间的中间位置 mid = strat+(end-strat)/2
2. 用待查关键字key值与中间位置的关键字值进行比较；
3. 若相等，则查找成功
4. 若大于，则在后（右）半个区域继续进行折半查找
5. 若小于，则在前（左）半个区域继续进行折半查找
6. 重复上述步骤。

方式一：非递归

    public static int search(int key, int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (key< arr[mid]) {
                end = mid - 1;
            } else if (key > arr[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

测试

    public static void main(String[] args) throws InterruptedException {
       int[] a={1,2,3,6,7,9,12,23,45};
        System.out.println(DataTest.search(3,a));//输出2
    }

方式二：递归

 public static int search2(int key, int[] arr, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2;
        if (key < arr[mid]) {
            return search2(key, arr, start, mid - 1);
        } else if (key > arr[mid]) {
            return search2(key, arr, mid + 1, end);
        } else {
            return mid;
        }
    }

测试

  public static void main(String[] args) throws InterruptedException {
        int[] a = {1, 2, 3, 6, 7, 9, 12, 23, 45};
        System.out.println(DataTest.search2(3, a,0,a.length-1));//输出2
    }

為什麼start=mid + 1，為什麼end=mid - 1：因为每一次查找都要去掉中间值。举例{1, 2, 3, 4, 5, 6, 7, 8, 9,10}第一次二分mid （下标）为4，排除掉元素5，如果查找的数在上半段{1, 2, 3, 4}，start=0；end=4-1=3；下半段{6, 7, 8, 9,10} start=4+1=5；end=9