69、x的平方根
| class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
left, right, ans = 0, x, -1
while left <= right:
mid = (right + left) // 2
if mid * mid <= x:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
|
81、搜索旋转排序数组
即使数组被旋转过，我们仍然可以利用这个数组的递增性，使用二分查找。对于当前的中点，
如果它指向的值小于等于右端，那么说明右区间是排好序的；反之，那么说明左区间是排好序的。
如果目标值位于排好序的区间内，我们可以对这个区间继续二分查找；反之，我们对于另一半区
间继续二分查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[mid] < nums[right]:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
elif nums[mid] > nums[right]:
if nums[mid] > target and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
elif nums[mid] == nums[left]:
left += 1
elif nums[mid] == nums[right]:
right -= 1
return False
|