【算法】数组查找之二分查找

心已赠人 2024-03-27 12:41 20阅读 0赞

## 二分查找 ##

### 要求： ###

*  有序
 *  无重复元素

### 题目 ###

*  [704. 二分查找 - 力扣（LeetCode）][704. _ - _LeetCode]
 *  [35. 搜索插入位置 - 力扣（LeetCode）][35. _ - _LeetCode]
 *  [34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）][34. _ - _LeetCode]
 *  [69. x 的平方根 - 力扣（LeetCode）][69. x _ - _LeetCode]
 *  [367. 有效的完全平方数 - 力扣（LeetCode）][367. _ - _LeetCode]
 *

### 模板 ###

#### 模板一 ####

> 区间是\[left,right\],条件是left<=right

public int search(int[] nums, int target) {
          
        //不需要判特  
        int left=0;  
        int right=nums.length-1;//right取 长度-1  
        while(left<=right){
        //条件是<=,因为当left=right的时候，是有意义的  
            int middle=left+(right-left)/2;//防止溢出 ,left+right 不一定能保证 <= MAX_VALUE
            if(nums[middle]==target){
          
                return middle;  
            }else if(nums[middle]>target){
          
                right=middle-1;  
            }else{
          
                left=middle+1;  
            }  
        }  
        return -1;//没有匹配结果  
    }

未查询到结果，查询结束时的状态  
right+1=left

#### 模板二 ####

> 区间是\[left,right),条件是left<right

public int search(int[] nums, int target) {
          
        //不需要判特  
        int left=0;  
        int right=nums.length;//right取 长度-1  
        while(left<right){
        //条件是<=,因为当left=right的时候，是有意义的  
            int middle=left+(right-left)/2;//防止溢出  
            if(nums[middle]==target){
          
                return middle;  
            }else if(nums[middle]>target){
          
                right=middle;  
            }else{
          
                left=middle+1;  
            }  
        }  
        return -1;//没有匹配结果  
    }

### 时间复杂度 ###

**O(n)=logn**

假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。  
最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素  
令n/2^k=1，  
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O(n)=O(logn).

> 参考资料：https://blog.csdn.net/ShelleyLittlehero/article/details/80739884

#### 查找目标 ####

有时候查找目标不单纯是一个值，可能需要提炼出一个表达式  
例如：https://leetcode.cn/problems/sqrtx/  
要找的目标就是·`middle * middle <= x`

public int mySqrt(int x) {
        
            int ans = 0;//
            // 查找一个数 ans*ans=x
            // 查找一个整数 ans*ans<=x ans取满足这个条件的最大整数
            // 范围是[0,x]
            // 采用二分查找法
            int left = 0;
            int right = x;
            while (left <= right) {
        
                int middle = left + (right - left) / 2;
                if ((long) middle * middle <= x) {
        //注意转换成long
                    ans = middle;
                    left = middle + 1;
                } else {
        
                    right = middle - 1;
                }
            }
            return ans;
    
    
        }

[704. _ - _LeetCode]: https://leetcode.cn/problems/binary-search/
[35. _ - _LeetCode]: https://leetcode.cn/problems/search-insert-position/
[34. _ - _LeetCode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[69. x _ - _LeetCode]: https://leetcode.cn/problems/sqrtx/
[367. _ - _LeetCode]: https://leetcode.cn/problems/valid-perfect-square/