目录

二分查找

基本介绍

二分查找是一种非常高效的算法,又称之为折半查找,顾名思义就是将查找的值和数组的中间值作比较【此处就要求这个数组必须是有序的了】 如果被查找的值小于中间值,就在中间值左侧数组继续查找;如果大于中间值,就在中间值右侧数组中查找;否则中间值就是要找的元素。

代码实现

递归方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
     * 二分查找(递归方式)
     *
     * @param arr
     * @param left
     * @param right
     * @param val
     * @return -1表示没找到
     */
    private static int recursiveBinarySearch(int[] arr, int left, int right, int val) {
        if (left < right) {
            int mid = (left + right) / 2;
            if (val == arr[mid]) {
                return mid;
            } else if (val > arr[mid]) {
                recursiveBinarySearch(arr, mid + 1, right, val);
            } else {
                recursiveBinarySearch(arr, left, mid - 1, val);
            }
        }
        return -1;
    }

迭代方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    /**
     * 二分查找(迭代)
     *
     * @param arr
     * @param val
     * @return
     */
    private static int commonBinarySearch(int[] arr, int val) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (val == arr[mid]) {
                return mid;
            } else if (val < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }