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

这篇具有很好参考价值的文章主要介绍了剑指 Offer 53 - I. 在排序数组中查找数字 I。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

二分查找

初始化：左边界 i=0 ，右边界 j=nums.length−1。
循环二分：当闭区间 [i, j] 无元素时跳出；

计算中点 m=(i+j)/2 （向下取整）；
若 nums[m]<target，则 target 在闭区间 [m+1,j] 中，因此执行 i=m+1；
若 nums[m]>target，则 target 在闭区间 [i,m−1] 中，因此执行 j=m−1；
若 nums[m]=target，则右边界 right 在闭区间 [m+1,j] 中；左边界 left 在闭区间 [i,m−1] 中。因此分为以下两种情况：
- 若查找右边界 right ，则执行 i=m+1；（跳出时 i 指向右边界）
- 若查找左边界 left ，则执行 j=m−1；（跳出时 j 指向左边界）

返回值：应用两次二分，分别查找 right 和 left ，最终返回 right−left−1 即可。

求比target大的值

        while(left <= right){
            int mid = left + ((right-left)>>1);
            if(nums[mid] <= target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

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

求比taget小的值

        while(left <= right){
            int mid = left + ((right-left)>>1);
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

剑指 Offer 53 - I. 在排序数组中查找数字 I
最终直接l-r-1即可，完整代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + ((right-left)>>1);
            if(nums[mid] <= target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        int r = left;
        if(right >= 0 && nums[right] != target) return 0;
        left = 0;
        right = nums.length-1;
        while(left <= right){
            int mid = left + ((right-left)>>1);
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        int l = right;
        return r - l - 1;
    }
}