题目

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

思路1

• 一般来说，首先想到的是使用一个变量，从头开始遍历整个数组，记录target数组出现的次数，但是这样的时间复杂度是O(n)，还是不够高效
• 题目说了，是排序数组，一想到排序数组，我们可以想到使用二分法：
  • 找出第一个target所在的位置和最后一个target所在的位置，那么出现的次数就是end - start + 1了

代码

class Solution {
    public int search(int[] nums, int target) {
        
        // 获取第一个和最后一个target所在数组的位置
        int start = getFirst(nums, 0, nums.length-1, target);
        int end = getLast(nums, 0, nums.length-1, target);

        // 只要start和end位置在在数组里面，就说明存在，否则返回0
        if (start >= 0 && end >= 0) {
            return end - start + 1;
        }
        return 0;
    }

    // 找到target所在数组第一次出现位置的下标
    public int getFirst(int[] nums, int start, int end, int target) {
        if (start > end) {
            return -1;
        }

        int midIndex = start + (end - start) / 2;
        int midValue = nums[midIndex];

        if (target == midValue) {
            // 递归的结束条件
            // 当前就是第一个的情况：不是最左边的元素并且和前一个元素不相等、是最左边的元素
            if ((midIndex != 0 && target != nums[midIndex - 1]) || midIndex == 0) {
                return midIndex;
            } else {
                end = midIndex - 1;
            }
        } else if (target > midValue) {
            start = midIndex + 1;
        } else {
            end = midIndex - 1;
        }

        // 根据新的start和end进行查找，找到后一路返回
        return getFirst(nums, start, end, target);
    }

    // 找到target所在数组最后一次出现位置的下标
    public int getLast(int[] nums, int start, int end, int target) {
        if (start > end) {
            return -1;
        }

        int midIndex = start + (end - start) / 2;
        int midValue = nums[midIndex];

        if (target == midValue) {
            if ((midIndex != nums.length-1 && target != nums[midIndex+1]) || midIndex == nums.length-1) {
                // 找到就返回
                return midIndex;
            } else {
                // 右边还有与target相等的数，那么将start指向 midIndex+1，二分查找右边
                start = midIndex + 1;
            }
        } else if (target > midValue) {
            // 如果target大于midValue也是二分查找右边
            start = midIndex + 1;
        } else {
            // 如果小于的话，就二分查找左边
            end = midIndex - 1;
        }

        return getLast(nums, start, end, target);
    }
}

复杂度分析

• 时间复杂度：\(O(logN)\)
• 空间复杂度：\(O(1)\)