【算法】二分查找算法

发表于 阅读次数：

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/**
 * 二分查找，从有序的数组中找到目标值
 *
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};

        System.out.println("找-1的下标：" + bSearch(arr, -1));
        System.out.println("找1的下标：" + bSearch(arr, 1));
        System.out.println("找2的下标：" + bSearch(arr, 2));
        System.out.println("找3的下标：" + bSearch(arr, 3));
        System.out.println("找4的下标：" + bSearch(arr, 4));
        System.out.println("找5的下标：" + bSearch(arr, 5));
        System.out.println("找6的下标：" + bSearch(arr, 6));
        System.out.println("找7的下标：" + bSearch(arr, 7));
        System.out.println("找8的下标：" + bSearch(arr, 8));
        System.out.println("找9的下标：" + bSearch(arr, 9));
        System.out.println("找10的下标：" + bSearch(arr, 10));

        System.out.println("从null中找1的下标：" + bSearch(null, 1));
        System.out.println("从{}中找1的下标：" + bSearch(new int[]{}, 1));
        System.out.println("从{1}找1的下标：" + bSearch(new int[]{1}, 1));
        System.out.println("从{1}找2的下标：" + bSearch(new int[]{1}, 2));
    }

    private static int bSearch(int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int first = 0;
        int last = arr.length - 1;
        while (first <= last) {

            // 取中间值
            int mid = (first + last) >> 1;

            if (arr[mid] == target) { // 中间值正好是要找的目标值
                return mid;
            } else if (arr[mid] > target) { // 中间值大于目标值，在左边找
                last = mid - 1;
            } else { // 中间值小于目标值，在右边找
                first = mid + 1;
            }
        }

        return -1;
    }
}/* 输出：
找-1的下标：-1
找1的下标：0
找2的下标：1
找3的下标：2
找4的下标：3
找5的下标：4
找6的下标：5
找7的下标：6
找8的下标：7
找9的下标：8
找10的下标：-1
从null中找1的下标：-1
从{}中找1的下标：-1
从{1}找1的下标：0
从{1}找2的下标：-1
 */

旋转数组的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/**
 * 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]，
 * 这样的。请问，给定这样一个旋转数组，求数组中的最小值。
 *
 */
public class BinaryExtendSearch {
    public static void main(String[] args) {
        System.out.println("{5, 6, 7, 8, 9, 1, 2, 3, 4} 找最小值，应该是1：" + bExtendSearch(new int[]{5, 6, 7, 8, 9, 1, 2, 3, 4}));
        System.out.println("{1, 2, 3, 4}找最小值，应该是1：" + bExtendSearch(new int[]{1, 2, 3, 4}));
        System.out.println("{1, 0, 1, 1, 1}找最小值，应该是0：" + bExtendSearch(new int[]{1, 0, 1, 1, 1}));
        System.out.println("{1, 1, 1, 1, 1}找最小值，应该是1：" + bExtendSearch(new int[]{1, 1, 1, 1, 1}));

    }

    private static int bExtendSearch(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        // 取最右端数据为目标值
        int target = arr[arr.length - 1];

        int first = 0;
        int last = arr.length - 1;
        while (first < last) {
            // 提前结束
            if (arr[first] < arr[last]) {
                return arr[first];
            }

            // 取中值
            int mid = (first + last) >> 1;

            // 如果中间值大于目标值，最小值在右边
            if (arr[mid] > target) {
                first = mid + 1;
                continue;
            }

            // 如果中间值小于目标值，最小值在左边，目标值成为中间值
            if (arr[mid] < target) {
                last = mid;
                target = arr[mid];
                continue;
            }

            // 其它情况，中间值==目标值
            last--;
        }

        return arr[first];
    }
}/*输出
{5, 6, 7, 8, 9, 1, 2, 3, 4} 找最小值，应该是1：1
{1, 2, 3, 4}找最小值，应该是1：1
{1, 0, 1, 1, 1}找最小值，应该是0：0
{1, 1, 1, 1, 1}找最小值，应该是1：1
*/