0%

算法 - 二分查找

发表于 更新于

给定一个有序数组，查找数组中某个元素的索引。

原理： 每次将搜索区间一分为二，比较目标值和中心值大小，再决定下一步要从左区间搜索还是右区间搜索。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
@Test
    public void testBinarySearch() {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // -- output :  1
    System.out.println(binarySearch(arr, 2));
}

private int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        //每次找到中心点，且要防止整数溢出。
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            //如果目标值大于中心值，则从右侧开始找
            low = mid + 1;
        } else {
            //如果目标值小于中心值，则从左侧开始找
            high = mid - 1;
        }
    }
    return -1;
}