对于区间[a，b]上连续不断且f(a)·f(b)<0的函数y=f(x)，通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值。

1.适用场景

  • 有序的数组，没有重复的数据元组
  • 使用场景：数据量较大

2.算法简述

  • 如果 value==arr[mid],中间值正好等于要查找的值，则返回下标，return mid;
  • 如果 value<arr[mid],要找的值小于中间的值，则再往数组的小端找，high=mid-1;
  • 如果 value>arr[mid],要找的值大于中间的值，则再往数组的大端找，low=mid+1;

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class dichotomySearch {
    public static int search(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = (start + end) / 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) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int key = 6;
        int index = search(arr, key);
        System.out.println(index);
    }
}