Algorithms/src/main/java/cn/codepub/algorithms/strings/BinarySearch.java at master · shijiebei2009/Algorithms · GitHub

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package cn.codepub.algorithms.strings;

/**
 * <p>
 * Created with IntelliJ IDEA. 2015/10/15 17:15
 * </p>
 * <p>
 * ClassName:BinarySearch
 * </p>
 * <p>
 * Description:二分查找
 * 注意点：数组在传递进来之前一定是排好序的数组，采用递归实现的方法一定要提供出口
 * </P>
 *
 * @author Wang Xu
 * @version V1.0.0
 * @since V1.0.0
 */
public class BinarySearch {

    /**
     * 递归方式实现二分查找
     *
     * @param nums  查找的数组
     * @param start 开始下标
     * @param end   结束下标
     * @param key   查找元素
     * @return 查找元素的下标，当未查到的时候，返回-1
     */
    private static int recursionBinarySearch(int[] nums, int start, int end, int key) {
        if (start > end) {
            return -1;
        }
        int mid = start + ((end - start) >> 1);
        if (nums[mid] == key) {
            return mid;
        } else if (nums[mid] > key) {
            //说明key在当前分组的左半边
            return recursionBinarySearch(nums, start, mid - 1, key);
        } else {
            //在右半边
            return recursionBinarySearch(nums, mid + 1, end, key);
        }


    }

    /**
     * 非递归方式实现二分查找
     *
     * @param nums 查找的数组
     * @param key  查找元素
     * @return 查找元素的下标，当未查到返回-1
     */
    private static int nonRecursionBinarySearch(int[] nums, int key) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            //防止(start + end) >>1 溢出
            //JDK中的Arrays.binarySearch使用(low + high) >>> 1;
            int mid = start + ((end - start) >> 1);
            if (nums[mid] == key) {
                return mid;
            } else if (nums[mid] > key) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 11};
        int i = recursionBinarySearch(nums, 0, nums.length - 1, 11);
        System.out.println(i);
        i = recursionBinarySearch(nums, 0, nums.length - 1, 12);
        System.out.println(i);
        i = recursionBinarySearch(nums, 0, nums.length - 1, 0);
        System.out.println(i);
        i = nonRecursionBinarySearch(nums, 11);
        System.out.println(i);
        i = nonRecursionBinarySearch(nums, 12);
        System.out.println(i);
        i = nonRecursionBinarySearch(nums, 0);
        System.out.println(i);
        nums = new int[]{1};
        i = recursionBinarySearch(nums, 0, nums.length - 1, 1);
        System.out.println(i);
        i = nonRecursionBinarySearch(nums, 1);
        System.out.println(i);
    }
}