JAVA二分查找法

算法思想

二分查找，又叫折半查找，要求待查找的序列是有序的。每次取中间位置的值与待查关键字比较，如果中间位置的值比要找的值大，则在左边部分循环查找，如果中间位置的值比待查关键字小，则在后边部分循环查找。直到查找到了为止。

时间复杂度

O(n) = O(log2n)

源码

/**
 * 二分查找法
 */
public class BiSearch {

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int a = 5;
        System.out.println("查找的数下标为：" + biSearch(arr, a));
        // 输出结果：查找的数下标为：6
    }

    private static int biSearch(int[] array, int a) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (array[mid] == a) {
                return mid + 1;
            } else if (array[mid] < a) { //如果此时中间数小于查找的数，则向右查找
                left = mid + 1;
            } else { //否则向左查找
                right = mid - 1;
            }
        }
        return -1;
    }
}