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

╰半橙微兮° 2024-03-23 16:37 39阅读 0赞

#### 目录 ####

*   *  二分查找

题目来源  
[剑指 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;
                }
            }

![在这里插入图片描述][3d277a7148be47058ea7d1819ef73c54.png]

求比taget小的值

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

![在这里插入图片描述][15f87b9a4599414ea9afeb50c871ba27.png]  
最终直接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;
        }
    }

![在这里插入图片描述][c4b29e5ca3554060afc3dfd9fa1daeaf.png]

[Offer 53 - I. _ I]: https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
[3d277a7148be47058ea7d1819ef73c54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2de41cd037be48c4a97ad5edb5ac4bc4.png
[15f87b9a4599414ea9afeb50c871ba27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/ffce66e2b27f4012996d47cb96543fe7.png
[c4b29e5ca3554060afc3dfd9fa1daeaf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/1493337bdf644c70b4c7618b11aa34f5.png