二分查找以及扩展

public class BinarySearch {

    /**
     * 经典的二分查找： 数组中的元素是升序的，并且没有重复
     * @param arr
     * @param value
     * @return
     */
    public static int bsearch(int[] arr, int value){
        if(arr == null || arr.length == 0){
            return -1;
        }

        int low = 0 ;
        int high = arr.length - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] == value){
                return mid;
            }else if(arr[mid] < value){
                //需要在当前区间的右侧继续查找
                low = mid+1;
            }else{
                //需要在当前区间的左侧继续查找
                high = mid-1;
            }
        }
        return -1;
    }


    //变形1.查找第一个值等于给定值的元素
    public static int bsearchFirstEq(int[] arr, int value){
        if(arr == null || arr.length == 0){
            return -1;
        }

        int low = 0 ;
        int high = arr.length - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] > value){
                high = mid-1;
            }else if(arr[mid] < value){
                low = mid+1;
            }else{
                if(mid == 0 || arr[mid-1] < value){
                    return mid;
                }else{
                    high = mid-1;
                }
            }
        }
        return -1;
    }

    //变形2.查找最后一个值等于给定值的元素
    public static int bsearchLastEq(int[] arr, int value){
        if(arr == null || arr.length == 0){
            return -1;
        }

        int low = 0 ;
        int high = arr.length - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] < value){
                low = mid+1;
            }else if(arr[mid] > value){
                high = mid-1;
            }else{
                if(mid == arr.length - 1 || arr[mid+1] > value){
                    return mid;
                }else{
                    low = mid+1;
                }
            }
        }
        return -1;
    }

    //变形3.查找第一个值大于等于给定值的元素
    public static int bsearchLastGE(int[] arr, int value){
        if(arr == null || arr.length == 0){
            return -1;
        }

        int low = 0 ;
        int high = arr.length - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] < value){
                low = mid+1;
            }else{
                if(mid == 0 || arr[mid-1] < value){
                    return mid;
                }else{
                    high = mid-1;
                }
            }
        }
        return -1;
    }

    //变形4.查找最后一个值小于等于给定值的元素
    public static int bsearchLastLE(int[] arr, int value){
        if(arr == null || arr.length == 0){
            return -1;
        }

        int low = 0 ;
        int high = arr.length - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] > value){
                high = mid-1;
            }else{
                if(mid == arr.length - 1 || arr[mid+1] > value){
                    return mid;
                }else{
                    low = mid+1;
                }
            }
        }
        return -1;
    }

    //变形5.局部最小值问题


}

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132