二分查找

发表于:，更新于:，By Guodong
大纲
  1. 1. 算法介绍
  2. 2. 代码实现
  3. 3. 玩笑

本文介绍归并排序的原理和实现。

算法介绍

二分查找是基于已排序数组的查找。
数组为a，返回数值为key的元素的index；不存在则返回-1。

  1. 创建两个游标low和high，如果key存在于a中，key的index必然满足low<=index<=high；
  2. 如果low<=high，计算中间值mid=(low+high)/2；
  3. 比较key和a[mid]的大小。如果a[mid]小于key，则low=mid+1，返回2；如果a[mid]>key，则high=mid-1，返回2；如果a[mid]=key，查询结束，返回mid；
  4. 返回-1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch(int[] a, long key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

玩笑

如果你是一个喷子，赶紧来给代码“找茬”吧，要是能找到你就厉害了。