# 二分查找算法

请对一个 有序数组 进行二分查找 {1,8, 10, 89, 1000, 1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示「没有这个数」。

二分查找可以使用递归和 非递归 实现，本次使用非递归方式实现。

# 思路分析

查找步骤：

首先确定该数组的中间下标
```
int  mid = (left + right)/2
```
1
然后让需要查找的数（findVal）和 arr[mid] 比较
1. findVal > arr[i]，说明要查找的数在右边
2. findVal < arr[i] ，说明要查找的数在左边
3. findVal == arr[i]，说明已经找到，就返回

什么时候结束递归？

找到则结束递归

未找到，则结束递归

当 left > right 时，表示整个数组已经递归完。

{1,8, 10, 89, 1000, 1234} 共 5 个
查找 -1
第一轮：
	mid = (0 + 5)/2 = 2 = 10 
   -1 < 10,往左边
第二轮：下面为什么是 + 1，而不是 + 2，是因为 mid 如果等于就返回了，已经判断过了，不需要再判断
	mid = (0 + 1)/2 = 0 = 1
   -1 < 1,往左边
第三轮：同理，这时 left = 0，right = -1
   left 就大于 right 了

1
2
3
4
5
6
7
8
9
10

# 代码实现

package cn.mrcode.study.dsalgtutorialdemo.datastructure.search;

import org.junit.Test;

/**
 * 二分查找
 */
public class BinarySearchTest {
    @Test
    public void binaryTest() {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1234};
        int findVal = 89;
        int result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = -1;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 123456;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 1;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));
    }

    /**
     * @param arr
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 未找到返回 -1，否则返回该值的索引
     */
    private int binary(int[] arr, int left, int right, int findVal) {
        // 当找不到时，则返回 -1
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        // 相等则找到
        if (midVal == findVal) {
            return mid;
        }
        // 要查找的值在右边，则右递归
        if (findVal > midVal) {
            // mid 的值，就是当前对比的值，所以不需要判定
            return binary(arr, mid + 1, right, findVal);
        }
        return binary(arr, left, mid - 1, findVal);
    }
}

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

测试输出

查找值 89：找到值，索引为：3
查找值 -1：未找到
查找值 123456：未找到
查找值 1：找到值，索引为：0

1
2
3
4

# 查找出所有值

请对一个 有序数组 进行二分查找 {1,8, 10, 89, 1000, 1000,1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示「没有这个数」。

增加难度：返回该值所有下标

  @Test
    public void binary2Test() {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1234};
        int findVal = 89;
        List<Integer> result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = -1;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 123456;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 1;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 1000;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));
    }

    /**
     * 查找所有符合条件的下标
     *
     * @param arr
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 未找到返回 -1，否则返回该值的索引
     */
    private List<Integer> binary2(int[] arr, int left, int right, int findVal) {
        // 当找不到时，则返回 -1
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        // 相等则找到
        if (midVal == findVal) {
            List<Integer> result = new ArrayList<>();
            // 如果已经找到，则先不要退出
            // 因为二分查找的前提是：对一个有序的数组进行查找
            // 所以，我们只需要，继续挨个的往左边和右边查找目标值就好了
            int tempIndex = mid - 1;
            result.add(mid);
            // 先往左边找
            while (true) {
                // 当左边已经找完
                // 或则找到一个不与目标值相等的值，就可以跳出左边查找
                if (tempIndex < 0 || arr[tempIndex] != midVal) {
                    break;
                }
                result.add(tempIndex);
                tempIndex--;
            }
            // 再往右边查找
            tempIndex = mid + 1;
            while (true) {
                if (tempIndex >= arr.length || arr[tempIndex] != midVal) {
                    break;
                }
                result.add(tempIndex);
                tempIndex++;
            }
            return result;
        }
        // 要查找的值在右边，则右递归
        if (findVal > midVal) {
            // mid 的值，就是当前对比的值，所以不需要判定
            return binary2(arr, mid + 1, right, findVal);
        }
        return binary2(arr, left, mid - 1, findVal);
    }

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

测试输出信息

查找值 89：找到值，索引为：[3]
查找值 -1：未找到
查找值 123456：未找到
查找值 1：找到值，索引为：[0]
查找值 1000：找到值，索引为：[5, 4]

1
2
3
4
5

← 顺序/线性查找算法插值查找算法 →