剑指offer--面试题53 - I. 在排序数组中查找数字 I

r囧r小猫 2023-02-18 06:27 50阅读 0赞

## 题目描述 ##

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

**示例 1:**

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

**示例 2:**

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

**限制：**

0 <= 数组长度 <= 50000

## 思路：排序数组的查找用二分法 ##

## 解决方法 ##

class Solution {
        
        public int search(int[] nums, int target) {
        
            int low=0, high= nums.length-1;
            //二分法确定右边界
            while(low <= high){
        
                int mid = (low+high) / 2;
                //等于target的时候也要右移，不断逼近右边界
                if(nums[mid] <= target){
          //注意这个地方的符号和运算
                    low = mid + 1;
                }else{
        
                    high = mid - 1;
                }
            }
            int right = low;  //右边界
            //二分法确定左边界
            low=0; high= nums.length-1;
            while(low <= high){
        
                int mid = (low + high) / 2;
                //等于target的时候也要左移，不断逼近左边界
                if(nums[mid] >= target){
        
                    high = mid - 1;
                }else{
        
                    low = mid + 1;
                }
            }
            int left = high;  //左边界
            return right-left-1;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616112206199.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA==,size_16,color_FFFFFF,t_70