35. Search Insert Position
https://leetcode.com/problems/search-insert-position/description/
left <= right, 以上实现方式有一个好处，就是当循环结束时，如果没有找到目标元素，那么left一定停在恰好比目标大的index上，right一定停在恰好比目标小的index上，所以个人比较推荐这种实现方式。所以直接返回left即可。
代码如下：
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return left
34. Find First and Last Position of Element in Sorted Array
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
如果直接相等的时候也向一个方向继续夹逼，如果向右夹逼，最后就会停在右边界，而向左夹逼则会停在左边界，如此用停下来的两个边界就可以知道结果了，只需要两次二分查找。实现中用到了在Search Insert Position中提到的方法，可以保证当搜索结束时，l和r所停的位置正好是目标数的后面和前面。
代码如下：
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
result = []
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
result.append(left)
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
result.append(right)
if result[0] > result[1]:
return [-1, -1]
return result
69. Sqrt(x)
https://leetcode.com/problems/sqrtx/description/
这道题一般采用数值中经常用的另一种方法：二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。
代码如下：
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
return -1
if x == 0 or x == 1:
return x
left = 1
right = x // 2 + 1
while left <= right:
mid = (left + right) // 2
if mid * mid <= x < (mid + 1) * (mid + 1):
return mid
if mid * mid > x:
right = mid - 1
else:
left = mid + 1
return -1
二分法在数值计算中非常常见，还是得熟练掌握。这个题目还有另一种方法，称为牛顿法。一般牛顿法是用数值方法来解一个f(y)=0的方程。牛顿法需要记住公式：
image.png
代码如下：
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
return -1
if x == 0 or x == 1:
return x
r = x
while r*r > x:
r = (r + x/r) // 2
return int(r)
其实，这道题还有一个巧妙的做法就是用位运算来进行求解，而且最多只需要判断16位，所以时间复杂度是O(1).
代码如下：
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
return -1
if x == 0 or x == 1:
return x
result = 0
bit = 1 << 16
while bit:
result |= bit
if result * result == x:
break
elif result * result > x:
result ^= bit
bit >>= 1
return result
74. Search a 2D Matrix
https://leetcode.com/problems/search-a-2d-matrix/description/
（1）Linear Search - O(m + n)
解法代码最容易实现，但时间复杂度最差，是线性的时间复杂度。思路即是从矩阵右上角开始向左搜索，找到第一个比目标小的元素再向下继续搜索即可。
代码如下：
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not len(matrix) or not len(matrix[0]):
return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target:
return True
if matrix[row][col] < target:
row += 1
else:
col -= 1
return False
（2）Double Binary Search - O(log(m) + log(n))
法只需要先按行查找，定位出在哪一行之后再进行列查找即可，所以就是进行两次二分查找。时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因而是O(1).
代码如下：
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not len(matrix) or not len(matrix[0]):
return False
left, right = 0, len(matrix) - 1
while left <= right:
mid = (left + right) // 2
if matrix[mid][0] == target:
return True
if matrix[mid][0] < target:
left = mid + 1
else:
right = mid - 1
row = right
left, right = 0, len(matrix[0]) - 1
while left <= right:
mid = (left + right) // 2
if matrix[row][mid] == target:
return True
if matrix[row][mid] < target:
left = mid + 1
else:
right = mid - 1
return False
（3）Divide and Conquer - O(log(n)) - CC 11.6
Divide and Conquer解法时间复杂度最优，但代码过于繁琐。思路是利用左上-右下对角线的中点将矩阵划为4块进行分治，代码详见CC150.
240. Search a 2D Matrix II
https://leetcode.com/problems/search-a-2d-matrix-ii/description/
上一题的第一种解法即可。
网友评论