69. x 的平方根

https://leetcode-cn.com/problems/sqrtx/
边界条件的判断是二分查找的唯一难点
start最终会留在平分刚好比x小的那个位置往右一点，也就是说 Binary Search - 图1

  1. class Solution:
  2.     def mySqrt(self, x: int) -> int:
  3.         if x < 2:
  4.             return x
  5.         start = 0
  6.         end = x
  7.         while start <
  8.         = end:
  9.             midpoint = start + (end-start)//2
  10.             if midpoint * midpoint < x:
  11.                 start = midpoint+1
  12.             elif midpoint * midpoint > x:
  13.                 end = midpoint-1
  14.             else:
  15.                 return midpoint
  16.         return start-1

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

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

  1. class Solution:
  2.     def findMin(self, nums: List[int]) -> int:
  3.         start = 0
  4.         end = len(nums)-1
  5.         while start<end:
  6.             midpoint = start + (end-start)//2
  7.             if nums[midpoint] > nums[end]:
  8.                 start = midpoint+1
  9.             else:
  10.                 end = midpoint
  11.         return nums[end]

33. 搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
其实相对简单的办法还是先找到数组旋转点，也就是最小值在哪里，然后将数组分为两段，根据target和两段的关系来查找
注意等号的选择！

  1. class Solution:
  2.     def search(self, nums: List[int], target: int) -> int:
  3.         left = 0
  4.         right = len(nums)-1
  6.         while left<=right:
  7.             mid = left + (right-left)//2
  8.             if nums[mid]==target:
  9.                 return mid
  11.             if nums[mid]>=nums[left]:
  12.                 if target>=nums[left] and target<nums[mid]:
  13.                     right = mid-1
  14.                 else:
  15.                     left = mid+1
  16.             else:
  17.                 if target>nums[mid] and target<=nums[right]:
  18.                     left = mid+1
  19.                 else:
  20.                     right = mid-1
  21.         return -1

1095. 山脉数组中查找目标值

https://leetcode-cn.com/problems/find-in-mountain-array/
有点类似在搜索旋转数组，但是这道题target有可能存在于左右两边各一个
关键在于先找到峰值，然后从峰值一分为二，在两侧都寻找

  1. # """
  2. # This is MountainArray's API interface.
  3. # You should not implement it, or speculate about its implementation
  4. # """
  5. #class MountainArray:
  6. #    def get(self, index: int) -> int:
  7. #    def length(self) -> int:
  9. class Solution:
  10.     def findMountainTop(self, mountain_arr: 'MountainArray') -> int:
  11.         left = 0
  12.         right = mountain_arr.length()-1
  13.         while left < right:
  14.             mid = left + (right-left)//2
  15.             mid_val = mountain_arr.get(mid)
  16.             if mid_val < mountain_arr.get(mid+1):
  17.                 left = mid+1
  18.             else:
  19.                 right = mid
  20.         return left
  22.     def binarySearch(self, arr, target, left, right, ascend=True):
  23.         while left <= right:
  24.             mid = left + (right-left)//2
  25.             if arr.get(mid) == target:
  26.                 return mid
  27.             elif arr.get(mid) < target:
  28.                 if ascend:
  29.                     left = mid+1
  30.                 else:
  31.                     right = mid-1
  32.             else:
  33.                 if ascend:
  34.                     right = mid-1
  35.                 else:
  36.                     left = mid+1
  37.         return -1
  40.     def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
  41.         peek_idx = self.findMountainTop(mountain_arr)
  42.         idx = self.binarySearch(mountain_arr, target, 0, peek_idx,True)
  43.         if idx!=-1:
  44.             return idx
  45.         else:
  46.             return self.binarySearch(mountain_arr, target, peek_idx, mountain_arr.length()-1, False)