二分查找算法

一、二分查找算法

二分查找算法又称为折半查找算法，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

二、算法思想

所要查询的数组是有序的，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

三、代码实现

package xzg.algorithm;

/**
 * 二分查找算法的优缺点：
 * 优点：比较次数少，查找速度快，平均性能好<p/>
 * 缺点：要求待查数据是有序的，且插入删除困难<p/>
 * 适用场景：数据变动少而查找频繁的有序列表<p/>
 */
public class BinarySearch {

    public static void main(String[] args) {

        //二分查找对数据的要求是有序的
        int array[] = {1, 3, 5, 11, 17, 21, 23, 28, 30, 32, 36, 50, 64, 78, 81, 95, 101};
        int searchKey = 95;
        //递归查找
//        int index = binarySearch(array, 0, array.length - 1, searchKey);
        //while循环查找
        int index = binarySearch(array, searchKey);
        String msg;
        if (index == -1) {
            msg = "数组中不含：" + searchKey;
        } else {
            msg = searchKey + "：在数组的位置是:" + index;
        }
        System.out.println(msg);
    }

    /**
     * 递归二分查找
     *
     * @param arr       有序数组
     * @param start     开始查找的索引位置
     * @param end       结束查找的索引位置
     * @param searchKey 待查找的关键字
     * @return 关键字在索引中的位置   -1则是未找到
     */
    public static int binarySearch(int arr[], int start, int end, int searchKey) {
        //初始化中间位置
        int mid = (end - start) / 2 + start;
        //找到要查找的关键字字段，则返回索引
        if (arr[mid] == searchKey) {
            return mid;
        }
        if (start >= end) {
            //数组查找完后仍未找到关键字，则返回-1
            return -1;
        } else if (searchKey > arr[mid]) {
            //说明关键字在以mid为分界线的右边区域，再次递归调用
            return binarySearch(arr, mid + 1, end, searchKey);
        } else if (searchKey < arr[mid]) {
            //说明关键在以mid为分界线的左边区域，再次递归调用
            return binarySearch(arr, start, mid - 1, searchKey);
        }
        return -1;
    }

    /**
     * while循环二分查找
     *
     * @param arr           有序数组
     * @param searchKey     待查找的关键字
     * @return              关键字在索引中的位置   -1则是未找到
     */
    public static int binarySearch(int arr[], int searchKey) {
        int start = 0;
        int end = arr.length - 1;
        int mid = 0;

        while (start <= end) {//当start和end相等时，则说明数组已循环查询完
            //初始化中间位置
            mid = (start + end) / 2;
            if (searchKey == arr[mid]) {
                //找到要查找的关键字字段，则返回索引
                return mid;
            } else if (searchKey > arr[mid]) {
                //说明关键字在以mid为分界线的右边区域，再次循环执行
                start = mid + 1;
            } else if (searchKey < arr[mid]) {
                //说明关键在以mid为分界线的左边区域，再次循环执行
                end = mid - 1;
            }
        }
        //数据仍未找到则返回-1
        return -1;
    }
}

输出结果如下：

95：在数组的位置是:15

Process finished with exit code 0

四、算法分析

• 优点：比较次数少，查找速度快，平均性能好
• 缺点：要求待查数据是有序排序的
  时间复杂度：O(log2_n)

参考资料：
https://blog.csdn.net/maoyuanming0806/article/details/78176957