二分查找算法(代码实现)

注意:使用二分查找算法查找的前提是数组是有序的

实现一: 只返回一个索引(也就是数组中无重复值时)

/**
     * 二分查找(实现一: 返回一个值)
     */
public static int binarySearch(int [] arr,int left,int right,int findVal){
    int mid = ((right - left)/2) + left;
    System.out.println(right + "" +left);
    //我们后面要多次使用到arr[mid],所以就会多次需要计算arr的mid位置的值,所以我们就需要使用一个临时变量midVal接收我们的arr[mid]
    //那么接下来我们就只用使用midVal来代表arr[mid]的值,我们的midVal不用解析,我们的arr[mid]需要解析
    if (left > right){
        return -1;
    }
    /*
        这个时候我们一定要将mid = arr[mid]的操作一定要在if(left > right)操作只有执行,如果left > right的时候执行 计算的mid的值会越界,
        //所以我们要不然就不要执行 int midVal = arr[mid]操作了
         */
    int midVal = arr[mid];
    if(findVal > midVal){
        return binarySearch(arr,mid+1,right,findVal);
    }else if(findVal < midVal){
        return binarySearch(arr,left,mid-1,findVal);
    }else{
        return mid;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这里我们给出代码测试:

/**
     * 对二分查找只返回一个数值的版本进行测试
     * @param args
     */
public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,9,23};
    int i = Search.binarySearch(arr, 0, arr.length - 1, 3);
    System.out.println(i);

    int i1 = Search.binarySearch(arr,0,arr.length - 1,30);
    System.out.println(i1);
}
1
2
3
4
5
6
7
8
9
10
11
12

实现二: 返回多个数值的(这个时候我们要将多个数值以一个集合的形式返回)

/**
     * 二分查找(实现二: 返回多个值
     */
public static List<Integer> binarySearch2(int [] arr, int left, int right, int findVal){
    //这个时候我们也是使用递归实现: 所以首先我们就是要给出递归结束的条件
    if (left > right){
        //如果判断我们的left > right之后直接就返回一个空的集合就可以了,就表示找不到数据
        return new ArrayList<Integer>();
    }
    int mid = (right - left)/2 + left;
    int midVal = arr[mid];
    //如果判断出我们的left <= right的时候这个时候就要进行判断
    if (findVal > midVal) {
        return binarySearch2(arr,mid + 1,right,findVal);
    }else if (findVal < midVal){
        return binarySearch2(arr,left,mid-1,findVal);
    }else {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(mid);

        //接下来就要向左和向右扫描,这个时候就要使用到一个临时变量
        int temp = mid - 1;
        while (arr[temp] == midVal) {
            //之前我们可以做一个判断进行优化:
            if (temp < 0 || arr[temp] != midVal) {
                break;
            }
            arrayList.add(temp);
            temp -= 1;
        }
        temp = mid + 1;
        while (arr[temp] == midVal) {
            if (temp > arr.length || arr[temp] != midVal) {
                break;
            }
            arrayList.add(temp);
            temp += 1;
        }
        return arrayList;
    }
}
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

这里我们给出代码测试:

/**
     * 对二分查找返回多个值的版本进行测试
     */
@Test
public void test1(){
    int[] arr = {1,3,5,52,344,4343};
    List<Integer> rsl = Search.binarySearch2(arr,0,arr.length - 1,5);
    System.out.println(rsl);

    List<Integer> integers = Search.binarySearch2(arr,0,arr.length - 1,134243);
    System.out.println(integers);
}
1
2
3
4
5
6
7
8
9
10
11
12

补充:

我们如果在算法中要多次使用arr.length或者arr[nums]等等的时候我们可以将arr.length或则arr[nums]记录到一个临时变量中 —> 临时变量可直接使用,而arr.length和arr[nums]还需要解析

我们使用int mid = (right - left)/2 + left的时候一定要注意: 如果这个时候left > right的时候执行这个操作,那么这个mid就会越界

• 比如我们的right 如果是arr.length - 1 ,假如我们的left 此时是arr.length,按理现在left > right了就应该退出循环或者退出递归,但是这个时候如果没有退出,那么计算出来的mid就是 0 + arr.length,这个时候使用arr[mid]就会出现数组下标越界问题 —> 我们的长度为length的数组最后一个索引为arr.length -1;