# 『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:

• 若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元素
• 若相等，则找到了

• i + j = (m + n + 1) / 2
• 并且a[i-1] < a[j]， a[j-1] < a[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.

• 若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++

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].

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

C++

python

### 69. Sqrt(x)

Implement `int sqrt(int x)`.

Compute and return the square root of x.

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

C++

Python

C++

Python

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`.

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.

• 若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.

### 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.

### 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`.

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

C++

Java

Python

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

C++

Java

Python

### 3 thoughts on “『leetcode』二分搜索”

1. totoro says:

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

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

如果换成

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

就会报错 time limit exceed， 是什么原因？

• 。。。。优先级问题。 L + ((R- L)>>1)

• totoro says:

我傻了。。。