leetcode-二分查找相关

目录
  • 二分查找的基本框架
  • 寻找一个数——基本的二分查找
  • 寻找左侧边界的二分搜索
  • 寻找右侧边界的二分查找
  • lower_bound和upper_bound
  • 69
  • 81
  • 154
  • 540
  • 4

二分查找的基本框架

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

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

首先注意的点：计算 mid 时需要防止溢出。

代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。

TIPS：

加法乘法是否导致超过数据类型范围

浮点型精度在判断是否相等的影响

寻找一个数——基本的二分查找

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意，也可以排除size=0情况

    while(left <= right) { //注意
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}
  1. while的循环条件<=，而不是<

前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。

如果为后者，在lef=right时循环结束，则区间内还有一个值未被判断。

关键概念：搜索区间

  1. 为什么 left = mid + 1，right = mid - 1？

因为 mid 已经搜索过，应该从搜索区间中去除。

  1. 算法的缺陷？

比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

寻找左侧边界的二分搜索

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    //1 2 3 4 

    while (left < right) { // 注意
        int mid = (left + right) / 2;//等价
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}
  1. 这里改变了搜索区间的定义：左闭右开
  2. 返回值left可以理解为，小于target的元素个数
  3. 为什么能搜索左边界了？

关键在于对于 nums[mid] == target 这种情况的处理：

if (nums[mid] == target)
        right = mid;

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

完整代码：

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

寻找右侧边界的二分查找

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

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

答：类似地，关键点还是这里：

if (nums[mid] == target) {
    left = mid + 1;

当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。

lower_bound和upper_bound

头文件：

二分查找的函数有 3 个：

lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。

upper_bound(起始地址，结束地址，要查找的数值) 返回的是 第一个大于待查找数值 出现的位置。

binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

69

x的平方根
对区域内二分查找，并且算是寻找左边界的类型
（如果不让用sqrt函数）
还有牛顿迭代法

class Solution {
public:
    int mySqrt(int x) {
        long long int left=0;
        long long int right=x;
        
        while(left<=right){
            long long int middle=left+(right-left)/2;
            long long int value=middle*middle;

            if(value==x){
                return middle;
            }else if(valuex){
                right=middle-1;
            }
        }

        return right;

    }
};

81

搜索旋转排序数组2
说明还是存在有序性，判断哪一部分有序性，利用二分查找

class Solution {
public:
    bool search(vector& nums, int target) {
        int length=nums.size();
        if(length==0){
            return false;
        }else if(length==1){
            return nums[0]==target?true:false;
        }

        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int middle=(left+right)/2;

            if(nums[middle]==target){
                return true;
            }else if(nums[left]==nums[middle]&&nums[right]==nums[middle]){  //两侧和中间相同，缩减区间
                left++;
                right--;
            }else if(nums[middle]>=nums[left]){ //左侧有序
                if(target>=nums[left]&&target<=nums[middle]){
                    right=middle-1;
                }else{
                    left=middle+1;
                }
            }else{  //右侧有序
                if(target>=nums[middle]&&target<=nums[right]){
                    left=middle+1;
                }else{
                    right=middle-1;
                }
            }
        }

        return false;
    }
};

154

//154 寻找旋转排序数组中的最小值2
//仍然应用二分查找的思想 且 最小值两侧的数据关系

class Solution {
public:
    int findMin(vector& nums) {
        //题干说明nums不存在为空
        int length=nums.size();
        if(length==1)
            return nums[0];

        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int middle=(left+right)/2;
            int ret=nums[right]-nums[middle];

            if(ret>0){
                right=middle;
            }else if(ret<0){
                left=middle+1;
            }else if(ret==0){
                right--;
            }          
        }
        //return什么，想好了再拿小示例验证一下
        return nums[left];
    }
};

540

//540 有序数组中的单一元素
//暴力法
class Solution {
public:
    int singleNonDuplicate(vector& nums) {
        //根据题目要求，应该不可能出现size=0
        int length=nums.size();
        if(length==1){
            return nums[0];
        }
        for(int i=1;i
//540 有序数组中的单一元素
//二分查找：要注意很多细节
class Solution {
public:
    int singleNonDuplicate(vector& nums) {
        //根据题目要求，应该不可能出现size=0
        int left=0;
        int right=nums.size()-1;
        while(left!=right){
            int middle=left+(right-left)/2;
            bool LeftTag=(nums[middle]==nums[middle-1]);
            bool RightRag=(nums[middle]==nums[middle+1]);
            if(!LeftTag && !RightRag){
                return nums[middle];
            }else if(LeftTag){
                if((middle-left-1)%2==0){
                    left=middle+1;
                }else{
                    right=middle-2;
                }
            }else if(RightRag){
                if((middle-left)%2==0){
                    left=middle+2;
                }else{
                    right=middle-1;
                }
            }
        }   
        return nums[left];
    }
};

优化：只对偶数索引二分搜索

4

寻找两个正序数组的中位数

  1. 最简单：归并两个数组可直接选择中位数
class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        vector Ret(nums1.size()+nums2.size());
        merge(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),Ret.begin());
        return (Ret[(Ret.size()+1)/2-1]+Ret[(Ret.size()+2)/2-1])/2.0;
    }
};

理论时间复杂度和空间复杂度都是O(n)，merge函数中自带sort
2. 稍微对上一种解法进行优化，直接利用双指针在两个有序数组中查询中位数
空间复杂度节省到O(1)
3. 对两个有序数组同时使用二分查找。相较于第二种其实就是，原本一个一个比较的过程利用二分查找跳过没必要遍历的元素。

class Solution {
public:
    int GetKthElement(const vector &nums1,const vector &nums2,int k){
        int length1=nums1.size();
        int length2=nums2.size();
        int index1=0,index2=0;

        while(1){

            //把超过边界的情况放在前面，k==1放在前面会报错
            if(index1==length1){
                return nums2[index2+k-1];
            }
            if(index2==length2){
                return nums1[index1+k-1];
            }
            if(k==1){
                return min(nums1[index1],nums2[index2]);
            }

        
            //正常情况
            int Newindex1=min(length1-1,(index1+k/2-1));
            int Newindex2=min(length2-1,(index2+k/2-1));
            if(nums1[Newindex1]<=nums2[Newindex2]){
                k-=(Newindex1-index1+1);
                index1=Newindex1+1;
            }else{
                k-=(Newindex2-index2+1);
                index2=Newindex2+1;
            }
        }

    }

    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        int length=nums1.size()+nums2.size();
        if(length%2==0){
            int a=GetKthElement(nums1,nums2,length/2);
            int b=GetKthElement(nums1,nums2,length/2+1);
            return (GetKthElement(nums1,nums2,length/2)+GetKthElement(nums1,nums2,length/2+1))/2.0;
        }else{
            return GetKthElement(nums1,nums2,length/2+1);
        }
    }
};
leetcode刷题

相关

LeetCode刷题总结-数组篇（上）

LeetCode刷题之DP算法

【leetcode刷题tips】数字之间的关系

[LeetCode刷题记录]39 组合总和

leetcode刷题-剑指offer-35题

leetcode刷题目录

20220227LeetCode刷题 最优除法

【LeetCode刷题笔记】力扣杯2022春季竞赛记录

LeetCode刷题1：反转链表

【LeetCode刷题】最长同值路径：妙解

标签