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

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制：

0 <= 数组长度 <= 50000

解一：找到出现的数字再找到数字的左右端点

• 使用二分查找法找到数字后，再循环找到左右两端点

• 时间复杂度：二分查找的时间复杂度为O(logn)，但是当数组中元素全是要寻找的数字时，左右两端点寻找的时间复杂度O(n)。可以考虑改进二分查找优化速度

• 空间复杂度：O(1)

class Solution {
    public static int search(int[] nums, int target) {
        int res = 0;
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;
        if(nums.length==1 && nums[0]==target){
            return 1;
        }
        boolean flag = false;
        while (left <= right) {
            if (nums[mid] > target) {
                right = mid - 1;
                mid = (left + right) / 2;
            }else  if(nums[mid]<target){
                left=mid+1;
                mid = (left + right) / 2;
            }else{
                flag=true;
                break;
            }
        }
        if(flag){
            left=mid;
            right=mid;
            while(right<nums.length-1 && nums[right]==nums[right+1] ){
                right++;
            }
            while(left>0 && nums[left]==nums[left-1]){
                left--;
            }
            res=right-left+1;
        }
        return res;
    }
}

解二：优化二分查找（迭代）

使用二分查找直接查找数字的左右边界，以左边界为例

• 令返回值res初值为-1

• 当查到mid==target时，说明左边界在mid左边或者是mid本身

• 如果mid已经是第一个数，或者mid-1的数不等于target，说明左边界是mid本身，res=mid

• 否则，说明左边界在mid左边，令right=mid-1，并退出循环

• 如果res==-1，说明数字中不包含该数字

class Solution {
    public static int search(int[] nums, int target) {
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        int res = 0;
        if(left>-1 && right>-1){
            res=right-left+1;
        }
        return res;
    }
    public static int searchLeft(int[] nums, int target) {
        int left = 0;
        int res = -1;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == nums[mid]) {
                if (mid == 0 || nums[mid - 1] != target) {
                    res = mid;
                    break;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    public static int searchRight(int[] nums, int target) {
        int left = 0;
        int res = -1;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == nums[mid]) {
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    res = mid;
                    break;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
           
}

解三：优化二分查找（递归）

class Solution {
     public static int search(int[] nums, int target) {
        int left = searchLeft(nums, target, 0, nums.length - 1);
        int right = searchRight(nums, target, 0, nums.length - 1);
        int res = 0;
        if (left > -1 && right > -1) {
            res = right - left + 1;
        }
        return res;
    }

    public static int searchLeft(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (target == nums[mid]) {
            if (mid == 0 || nums[mid - 1] != target) {
                return mid;
            } else {
                right = mid - 1;
            }
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        return searchLeft(nums, target, left, right);
    }

    public static int searchRight(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (target == nums[mid]) {
            if (mid == nums.length - 1 || nums[mid + 1] != target) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }

        return searchRight(nums,target,left,right) ;
    }
           
}

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

原文：https://www.cnblogs.com/simpleName/p/14626665.html