二分查找算法

 2016-05-07 17:24:24     算法  Java   651


导读: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

说明

采用二分查找算法,前提是数组a已经是正序,将n个元素分成大致相等的两部分,取a[n/2]x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。

二分查找算法充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果xa[n/2],则我们只要在数组a的右 半部继续搜索x。

二分查找算法图

代码

/**
 * Arrays.binarySearch源码
 * 采用二分查找算法
 */
public class Test1 {

    public static void main(String[] args) {
        int[] a = {10, 2, 5, 4, 9, 8, 1, 3, 6, 7};
        Arrays.sort(a);
        System.out.print("[");
        for (int i : a) {
            System.out.print(i + ",");
        }
        System.out.println("]");
        System.out.println(binarySearch(a, 0, 10, 4));
    }

    /**
     * @param a         已经排好序的数组
     * @param fromIndex 搜索范围的起始位置(包含)
     * @param toIndex   搜索范围的结束位置(不包含)
     * @param key       需要查询的关键字
     * @return 如果key包含在数组中,则返回对应的数组索引;
     * 否则返回 (-(插入点) - 1).
     * <p/>
     * 插入点 被定义为将键插入数组的那一点:即第一个大于此键的元素索引,如果数组中的所有元素都小于指定的键,则为 a.length
     */
    private static int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            //int mid = (low + high) / 2;
            int mid = (low + high) >>> 1;
            System.out.println("mid: " + mid);
            int midVal = a[mid];
            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid; // key found
            }
        }

        return -(low + 1);  // key not found.
    }
}

参考: