『leetcode』二分搜索

本次题解包括:

  • Median of Two Sorted Arrays
  • 33 Search in Rotated Sorted Array
  • 34 Search for a Range
  • 35 Search Insert Position
  • 69 Sqrt(x)
  • 74 Search a 2D Matrix
  • 81 Search in Rotated Sorted Array II
  • 153 Find Minimum in Rotated Sorted Array
  • 154 Find Minimum in Rotated Sorted Array II
  • 240 Search a 2D Matrix II

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:

题目地址:leetcode Median of Two Sorted Arrays

题意:

给定两个排好序的数组,求它们的中位数。

思路:

首先,求中位数需要注意奇数偶数的情况。

方法一

设nums1长度为m,nums2的长度为n,将问题转化为在两个排好序的数组中找第k = (m + n + 1) / 2 小的元素(若总数是偶数还需要找第k+1大的元素)。

为了方便说明,假设 m<=n

每次a_m= min(m, k/2),b_mid = k – a_m,然后比较A中第a_m个元素和B中第b_m个元素,即A[a_m – 1]和B[b_m – 1],

  • 若A[a_m – 1] < B[b_m – 1],则说明第k小的元素不可能出现在A中的前a_m个,也不可能出现在B中的b_m之后。即在A[a_m:],B[:b_m + 1]中查找第k – a_m元素。(因为a_m + b_m = k,不可能出现在A的a_m个的话,B中的前b_m个元素已经足够k-a_m个了)
  • 若A[a_m – 1] >B[b_m – 1],则说明第k小的元素不可能出现在B中的前b_m个,也不会再A中的a_m之后,因此,在A[a_m + 1],B[b_m:]中查找k – b_m元素
  • 若相等,则找到了

复杂度O(log(m + n))

 

方法二:

同样假设m <= n,我们需要找到的是一个i和一个j,这两个下标分别将两个数组划分为左右两部分:

当然i未必和j相等。若能找到一个这样的i和j,满足:

  • i + j = (m + n + 1) / 2
  • 并且a[i-1] < a[j], a[j-1] < a[i]

这两个条件使得a[i – 1], 和b[j – 1]恰好为在中间的数,谁大谁就是中位数,若m + n为,偶数,则还要考虑a[i]和a[j]中较小的数。(i=0或j=0或i = m或j = n的特殊情况之后讨论)

因此,可以二分枚举i,起始范围left= 0, right  = m,则j = (m + n + 1) / 2 – i,

  • 若a[i] < b[j – 1],则说明i太小,要增大i,left = i + 1
  • 若a[i – 1] > b[j],说明i太大,要减小i,right = i – 1
  • 否则找到了i和j的正确位置,看m + n是奇数的话直接返回max(a[i – 1], b [j- 1])即可,否则为(max(a[i – 1], b [j- 1]) + min(a[i], b[j])) / 2

现在讨论边界情况:

  • i = 0时,此时j = (m + n + 1) / 2,此时即可假设a[i-1]必定小于b[j],只需要看 a[i] > b[j -1]即可
  • i = m时,此时j = (n – m + 1) / 2 > 0,也可以说a[i] > b[j – 1],只需要看a[i – 1] < b[j]即可
  • j = 0和j = n同理

 

 

 

33.  Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

题目地址:leetcode Search in Rotated Sorted Array

题目大意给定一个排好序,但是经过旋转的数组(如0 1 2 4 5 6 7 变为 4 5 6 7 0 1 2),且该数组元素唯一。给定一个数,求其出现的下标,若不存在,返回-1

思路:

也是二分搜索。一个trick是A[L]  <= A[R]说明 [L,R]为升序

 

方法一 O(log n)

  • 若nums[mid] == target 没什么好说的,返回mid
  • 若nums[mid] < target
    • 若nums[mid] < nums[right] && target <= nums[right] ||  nums[mid] > nums[right]
      • 即右边有序且target在右边的范围内或者右边非有序则 left = mid + 1
      • 因为nums[mid] < target 所以若右边非有序,则左边一定有序,target一定大于左边的所有元素,只能在右边
    • 否则right = mid – 1
  • target  < nums[mid]
    • 若nums[left] < nums[mid] && nums[left] <=target
      • 即左边有序且target在左边的范围内  或者 左边无序列  right = mid – 1;
      • 因为target  < nums[mid] ,若左边无序则nums[mid]小于右边的所有元素,只能在左边。
    • 否则left = mid + 1

C++

 

方法二 O(log n)

直接看代码,很显然。。

C++

Python

 

 

 


 

34. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

题目地址:leetcode Search for a Range

题目大意:给定一个数组A,和一个要查找的数target,返回数组A中出现的位置(第一次出现和最后一次出现),如果不存在,为-1,-1

思路: 就是二分搜索找上下界。(可以先做35题)水~

C++

 

python

 

 


 

35 . Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

题目地址:leetcode Search Insert Position

题目大意: 给定一个排好序的数组和一个数,返回这个数插入的位置。

 

思路:水~二分

C++

python

 


 

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

题目地址:leetcode Sqrt(x)

题目大意:实现根号n的计算

思路:

方法一: 二分法

C++要用long long 防止越界,py弱类型好处体现出来了。。

C++

Python

 

方法二: 牛顿迭代法

可参考: https://en.wikipedia.org/wiki/Integer_square_root

C++

Python

 

方法三:位运算

猜测法,当前的 ans | (1 << i)的平方如果不大于x,那么说明当前的位数可以是1

C++

Python

 


 

74.  Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

Given target = 3, return true.

题目地址:leetcode Search a 2D Matrix

题目大意: 给定一个矩阵,这个矩阵中,每一行的元素均从小到大排好序,且每一行第一个元素大于上一行最后一个元素。给定一个数target,判断target是否存在。

思路:

  1. 两次二分。一开始先确定行,取每行最后一个数进行查找。之后在这一行进行查找该元素。
  2. 直接把矩阵看成一维的,即L=0,R=m*n-1,而每次matrix[mid/n][mid%n]即可。

 

C++方法一

 C++方法二

python方法二

 

 

 

81. Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

题目地址:leetcode Search in Rotated Sorted Array II

题目大意: 把33题的数组改为元素可以重复出现,给定一个target,判断其是否存在。

思路:

和33题相比不同的是,这题元素是可重复的,可重复对于我们的有序判断产生了影响。

原来我们直接A[L]  <= A[R]说明 [L,R]为升序,现在不行了,比如11131.

 

现在还是进行二分搜索。

  • 若nums[mid] == target,返回true
  • nums[left] < nums[mid]:  左边有序,同33题处理。
    • nums[left] <= target < nums[mid] : right = mid – 1
    • 否则left = mid + 1
  • nums[left] > nums[mid]:  右边有序,同33题处理。
    • nums[mid] < target <= nums[right] : left = mid + 1
    • 否则right = mid – 1
  • 否则说明nums[left] == nums[mid]
    • 无法判断应该取左还是右。 如11311111和11111131
    • 因此left+=1
    • 正因为此,最坏情况复杂度为O(n)

C++

 

Python

 

 

153. Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

传送门

题意:给定一个排好序,但是经过旋转的数组(数组中无重复元素),求该数组的最小值。

思路:类似前面的81题(排好序的旋转的数组中进行二分查找),这题也一样,A[L]<=A[R]说明数组有序,直接返回A[L]

 

 

154. Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

传送门

题意:给定一个排好序,但是经过旋转的数组(数组中有重复元素),求该数组的最小值。

思路:和上面一题不同在于这题有重复元素,仅有A[L]<A[R]时,返回A[L]。

 


 

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

Given target = 5, return true.

Given target = 20, return false.

题目地址:leetcode Search a 2D Matrix II

题目大意 : 给定一个矩阵,该矩阵满足:每一行和每一列均为升序。给定一个数target,让你判断这个数是否在矩阵中。

思路:

  • 直接想到的是二分搜索,对每一行进行一次二分,复杂度为O(mlogn)

C++

Java

Python

  • 第二种思路是设定初始点为最左下角或者最右上角。以最左下角为例,
    • 当matrix[i][j] == target: 返回true不解释
    • 当matrix[i][j] < target: 说明我们应该向右查找(行为升序)
    • 当matrix[i][j] > target::说明我们应该向上查找(列为降序)
    • 这样复杂度为O(m+n)

C++

Java

Python

初始点为右上角的Python代码。。

 

 

 

这是leetcode 二分搜索的题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > 『leetcode』二分搜索
本文地址:https://www.hrwhisper.me/leetcode-binary-search/

听说长得好看的已经打赏了

Leetcode . permalink.

3 thoughts on “『leetcode』二分搜索

  1. LZ 请教下 240. Search a 2D Matrix II 二分搜索方法 C++代码line 6

    int mid = (L + R) >> 1;

    如果换成

    int mid = L + (R-L) >> 1;

    就会报错 time limit exceed, 是什么原因?

Leave a Reply

Your email address will not be published. Required fields are marked *