欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[查找算法]二分查找法

程序员文章站 2023-12-22 12:25:52
...

二分查找法是经典的入门算法,以高效和广泛应用而著称.
算法是由静态方法rank() 实现的,它接受一个整数键和一个已经有序的int 数组作为参数。如果该键存在于数组中
则返回它的索引,否则返回-1。算法使用两个变量low 和high,并保证如果键在数组中则它一定在
a[low…high] 中,然后方法进入一个循环,不断将数组的中间键(索引为mid)和被查找的键比较。
如果被查找的键等于a[mid],返回mid;否则算法就将查找范围缩小一半,如果被查找的键小于
a[mid] 就继续在左半边查找,如果被查找的键大于a[mid] 就继续在右半边查找。算法找到被查找
的键或是查找范围为空时该过程结束。

基础形式:

    public static int rank(int key, int[] a)
    { // 数组必须是有序的
        int low = 0;
        int high = a.length - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (key < a[mid]) high = mid - 1;
            else if (key > a[mid]) low = mid + 1;
            else return mid;
        }
        return -1;		//返回-1意味着在数组中没有找到该键
    }

ss在Arrays类中已经内置了二分查找的方法binarySearch(数组,int key);

上一篇:

下一篇: