Skip to content

二分查找.md

Latest commit

 

History

History
704 lines (523 loc) · 18.1 KB

二分查找.md

File metadata and controls

704 lines (523 loc) · 18.1 KB
Raw

二分查找总结

H指数II

LeetCode中文

题解：二分查找，关键是找到二分判断的条件，参考如下题解的思路，二分的代码不用参考

https://leetcode.cn/problems/h-index-ii/solutions/2504326/tu-jie-yi-tu-zhang-wo-er-fen-da-an-si-ch-d15k

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int len = citations.size();
        int l = 0, r = len;
        while (l < r) {
            // +1处理，倾向于偏右计算m值，防止死循环
            int m = (l + r + 1) / 2;
            if (citations[len - m] >= m) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l;
    }
};

博客总结

二分搜索法总结

二分查找边界问题总结

x的平方根

LeetCode中文

LeetCode英文

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解答

为了缩短搜索时间，使用二分查找来寻找平方根。这里属于博主之前总结的二分搜索法小结中的第三类的变形，找最后一个不大于目标值的数。

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)
class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x <= 1:
            return x
        
        l = 0
        r = x
        while l < r:
            m = int((l + r) / 2)
            if m * m <= x:
                l = m+1
            else:
                r = m
                
        return r-1

寻找旋转排序数组中的最小值

LeetCode中文

LeetCode英文

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

解答

首先判断数组是否已经旋转，如果nums[0] < num[len-1]那么数组没有旋转，直接返回nums[0]；否则，数组旋转。

二分查找：定义两个指针l和r分别指向数组两端，取m = (r + l)/2，找到中间那个数nums[m]和nums[r]比较：

  1. 如果nums[m] < nums[r]，则在右半段搜索；
  2. 如果nums[m] > nums[r]，则在左半段搜索；

直到l和r相邻，返回nums[r]

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)
class Solution {
public:
    int findMin(vector<int>& nums) {
      if (nums.empty()) throw "nums is empty";
      int len = nums.size();
      if (nums[0] < nums[len - 1]) {
        return nums.front();
      }
      int l = 0, r = len - 1;
      while (l < r) {
        int m = (l + r) / 2;
        if (nums[m] > nums[r]) {
          l = m + 1;
        } else {
          r = m;
        }
      }
      return nums[r];
    }
};

寻找旋转排序数组中的最小值II

LeetCode中文

LeetCode英文

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

示例 2：

输入: [2,2,2,0,1]
输出: 0

说明：

这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

解答

思路和 寻找旋转排序数组中的最小值 一样,但是由于数组存在重复元素，会影响二分查找的效果，要特殊处理这种情况，当nums[m] == num[r]时，r左移直到nums[m] != nums[r]

  • 时间复杂度：O(log n)~O(n)
  • 空间复杂度：O(1)
class Solution {
public:
    int findMin(vector<int>& nums) {
      if (nums.empty()) throw "nums is empty";
      int len = nums.size();
      if (nums[0] < nums[len - 1]) {
        return nums.front();
      }
      int l = 0, r = len - 1;
      while (l < r) {
        int m = (l + r) / 2;
        if (nums[m] > nums[r]) {
          l = m + 1;
        } else if (nums[m] < nums[r]) {
          r = m;
        } else {
          --r;
        }
      }
      return nums[r];
    }
};

寻找峰值

LeetCode中文

LeetCode英文

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

说明: 你的解法应该是 O(logN) 时间复杂度的。

解答

二分查找，设左边缘和右边缘分别是l和r，找到中间值nums[mid]，需要判断到左半段还是右半段查找，由于题目假设nums[-1] = nums[n] = -∞，判断规则为：

  1. 如果nums[m] >= nums[m+1]，则峰值位于左半段，令r = m
  2. 如果nums[m] < nums[m+1]，则峰值位于右半段，令l = m+1
  • 时间复杂度：O(log n)
  • 空间复杂度：O(n)
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0,r = nums.size() - 1,mid;
        while(l < r)
        {
            mid = (l + r) >> 1;
            if(nums[mid] < nums[mid + 1])
                l = mid + 1;
            else if(nums[mid] >= nums[mid + 1])
                r = mid;
        }
        return l;
    }
};

搜索旋转排序数组

LeetCode中文

LeetCode英文

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解答

二分查找，关键是找到中间值之后，判断接下来在左半段还是右半段继续查找。根据旋转数组的规律，数组经过旋转之后会被分为两段升序段，找到中间值nums[m]之后，将它和搜索区域最右边元素nums[r]比较，处理情况如下：

  1. 如果nums[m] == target，则返回m
  2. 如果nums[m] > nums[r]，则中间值位于旋转数组的前一段升序段
    • 如果target < nums[m] && target >= nums[l]，则到m的左半段继续查找
    • 否则，到m的右半段继续查找
  3. 如果nums[m] <= nums[r]，则中间值位于旋转数组的后一段升序段
    • 如果target > nums[m] && target <= nums[r]，则到m的右半段继续查找
    • 否则，到m的左半段继续查找
  • 时间复杂度O(log n)
  • 空间复杂度O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {
      if (nums.empty()) return -1;
      int l = 0, r = nums.size() - 1;
      while (l < r) {
        int m = (l + r) / 2;
        if (target == nums[m]) {
          return m;
        }
        if (nums[m] > nums[r]) {
          if (target >= nums[l] && target <= nums[m]) {
            r = m;
          } else {
            l = m + 1;
          }
        } else {
          if (target > nums[m] && target <= nums[r]) {
            l = m + 1;
          } else {
            r = m;
          }
        }
      }
      return target == nums[r] ? r : -1;
    }
};

搜索旋转排序数组II

LeetCode中文

LeetCode英文

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

进阶:

  • 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解答

和 搜索旋转排序数组 一样还是二分查找，但是由于数组可能包含重复元素，所以当nums[m] == nums[r]的时候，将搜索区域的右边缘左移一个位置直到nums[m] != nums[r]。

  • 时间复杂度O(log n)
  • 空间复杂度O(1)
class Solution {
public:
    bool search(vector<int>& nums, int target) {
      if (nums.empty()) return false;
      int l = 0, r = nums.size() - 1;
      while (l < r) {
        int m = (l + r) / 2;
        if (nums[m] > nums[r]) {
          if (target >= nums[l] && target <= nums[m]) {
            r = m;
          } else {
            l = m + 1;
          }
        } else if (nums[m] < nums[r]) {
          if (target > nums[m] && target <= nums[r]) {
            l = m + 1;
          } else {
            r = m;
          }
        } else {
          --r;
        }
      }
      return nums[r] == target;
    }
};

在排序数组中查找元素的第一个和最后一个位置

LeetCode中文

LeetCode英文

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解答

二分查找，由于要找到目标值的第一个位置和最后一个位置。当中间值nums[m] == target时：

  1. 如果要找第一个位置，则向m的左半段继续二分查找，--r直到nums[m-1] != target为止;
  2. 如果要找最后一个位置，则向m的右半段继续二分查找，++l直到nums[m+1] != target为止；
  • 时间复杂度O(log n)
  • 空间复杂度O(1)
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1,-1};
        int len = nums.size();
        int l = 0,r = nums.size() - 1;
        int start = -1,end = -1;
        while(l <= r)
        {
            int m = l + (r-l)/2;
            if(nums[m] < target) l=m+1;
            else if(nums[m] > target) r = m-1;
            else
            {
                if(m == 0)
                {
                    start = 0;
                    break;
                }
                
                if(nums[m-1] != target)
                {
                    start = m;
                    break;
                }
                else r = m-1;
            }
        }
        
        if(l > r) return {-1,-1};
        
        l = 0;
        r = nums.size() - 1;
        while(l <= r)
        {
            int m = l + (r-l)/2;
            if(nums[m] < target) l = m+1;
            else if(nums[m] > target) r = m-1;
            else 
            {
                if(m == len-1)
                {
                    end = len-1;
                    break;
                }
                if(nums[m+1] != target)
                {
                    end = m;
                    break;
                }
                else l = m+1;
            }
        }
        
       return {start,end};
    }
};

简化代码

查找最后一个位置的时候，中间位置计算方法是m = (l + r +1)/2，这样使得中间值偏向右侧，防止无限循环。例如[8,8,10]，如果按照m = (l + r)/2来计算，在查找目标值最后一个位置的时候会无限循环

  • 时间复杂度O(log n)
  • 空间复杂度O(1)
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        if(nums.empty()) return res;
        int l = 0,r = nums.size() - 1;
        
        while(l < r)
        {
            int m = (l + r) / 2;
            if(nums[m] < target) l = m+1;
            else r = m;
        }
        
        if(nums[l] != target) return res;
        res[0] = l;
        
        l = 0,r = nums.size() - 1;
        while(l < r)
        {
            int m = (r + l + 1) / 2;
            if(nums[m] <= target) l = m;
            else r = m-1;
        }
        
        res[1] = l;
        
        return res;
    }
};

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

LeetCode中文

LeetCode英文

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解答

方法1

先合并两个有序数组为一个有序数组(参考 合并两个有序数组)，找到这个合并后的有序数组的中位数即可。

  • 时间复杂度O(m + n)
  • 空间复杂度O(m + n)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        
        vector<int> nums3(len1 + len2,0);
        int i = 0;
        int j = 0;
        int index = 0;
        while(i < len1 && j < len2)
        {
            if(nums1[i] < nums2[j])
                nums3[index++] = nums1[i++];
            else
                nums3[index++] = nums2[j++];
        }
        
        while(i < len1)
        {
            nums3[index++] = nums1[i++];
        }
        
        while(j < len2)
        {
            nums3[index++] = nums2[j++];
        }
        
        double res;
        int len3 = nums3.size();
        if((len3 & 0x1) == 0)
        {
            res = (double)(nums3[len3/2] + nums3[len3/2-1]) / 2;
        }
        else
        {
            res=(double)nums3[len3/2];
        }
        
        return res;
    }
};

方法2：二分查找

参见解法三

  • 时间复杂度O(log(m+n))
  • 空间复杂度O(1)
class Solution {
public:
    int recursion(const vector<int>& nums1, const vector<int>& nums2, int k, int start1, int start2) {
        int len1 = nums1.size(), len2 = nums2.size();
        if (start1 >= len1) return nums2[start2 + k - 1];
        if (start2 >= len2) return nums1[start1 + k - 1];
        if (k == 1) return min(nums1[start1], nums2[start2]);
        int n1 = min(start1 + k / 2 - 1, len1 - 1);
        int n2 = min(start2 + k / 2 - 1, len2 - 1);
        if (nums1[n1] < nums2[n2]) {
            return recursion(nums1, nums2, k - (n1 - start1 + 1), n1 + 1, start2);
        } else {
            return recursion(nums1, nums2, k - (n2 - start2 + 1), start1, n2 + 1);
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        int k1 = (len1 + len2 + 1) / 2, k2 = (len1 + len2 + 2) / 2;
        return double(recursion(nums1, nums2, k1, 0, 0) + recursion(nums1, nums2, k2, 0, 0)) / 2.0;
    }
};