剑指 Offer 53 - I. 在排序数组中查找数字 I

题目：

思路：

• 在排序数组中查找数字,首先想到二分查找，本题统计一个数字在排序数组中出现的次数，

• 可以理解为 找到最左边和最右边的这个数字，right - left + 1 就是数字的个数

• 二分查找在找目标数字时，找到mid是直接返回的，而边界二分查找，

• 比如左边界，找到mid之后不返回，继续让右边界减一，相当于向左寻找，最后返回最左边的边界

• 查找的时候需要注意判断左右边界的返回值，比如查找左边界时，所给target比所给数组的所有数都要大，那么就会返回一个大于等于数组长度的一个数，肯定是不能用的，同样查找右边界也是这个道理

• 还有一种情况，target还是不存在于数组，但是他的数值在所给数组数值最大最小之间，这时也要判断一下

• 以上两种不存在都让函数返回-1，那么

• 如果返回的left和right都为-1，则表示不存在找不到

• 如果返回的left和right相等，则表示只存在那一个

题解：

public class Solution {

    /**
     *剑指 Offer 53 - I. 在排序数组中查找数字 I
     *
     * 在排序数组中查找数字,首先想到二分查找，本题统计一个数字在排序数组中出现的次数
     * 可以理解为 找到最左边和最右边的这个数字，right - left + 1 就是数字的个数
     *
     * 二分查找在找目标数字时，找到mid是直接返回的，
     * 而边界二分查找，比如左边界，找到mid之后不返回，继续让右边界减一，相当于向左寻找
     * 最后返回最左边的边界
     *
     * 查找的时候需要注意判断左右边界的返回值
     * 比如查找左边界时，所给target比所给数组的所有数都要大，那么就会返回一个大于等于数组长度的一个数，肯定是不能用的
     * 同样查找右边界也是这个道理
     * 还有一种情况，target还是不存在于数组，但是他的数值在所给数组数值最大最小之间，这时也要判断一下
     *
     * 以上两种不存在都让函数返回-1，那么
     * 如果返回的left和right都为-1，则表示不存在找不到
     * 如果返回的left和right相等，则表示只存在那一个
     */
    public int search(int[] nums, int target) {

        //查找左边界
        int left = searchLeft(nums,target);
        //查找右边界
        int right = searchRight(nums,target);

        //判断结果
        if (left == -1 && right == -1){
            return 0;
        }else if (left == right){
            return 1;
        }

        return right - left + 1;
    }

    private int searchRight(int[] nums, int target) {

        int l = 0,r = nums.length - 1;

        while (l <= r){

            int mid = r + (l - r)/2;

            if (target > nums[mid]){
                l = mid + 1;
            } else if (target < nums[mid]){
                r = mid - 1;
            } else {
                //向右边靠
                l = mid + 1;
            }
        }
        //判断是否存在
        if (r < 0 || nums[r] != target){
            return -1;
        }

        return r;
    }

    private int searchLeft(int[] nums, int target) {

        int l = 0,r = nums.length - 1;

        while (l <= r){

            int mid = r + (l - r)/2;

            if (target > nums[mid]){
                l = mid + 1;
            } else if (target < nums[mid]){
                r = mid - 1;
            } else {
                //向左边靠
                r = mid - 1;
            }
        }
        //判断是否存在
        if (l >= nums.length || nums[l] != target){
            return -1;
        }

        return l;
    }
}
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