原题Leetcode 35. Search Insert Position
Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.
题目要求以O(log n)的时间复杂度完成，又因为是sorted array of distinct integers，我们这里可以考虑用常规的二分法进行解题
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, nums - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target # 由于是distinct integers，这里可以直接返回mid
return mid
elif nums[mid] < target:
# 由于nums[mid]比target小，所以插入的地方必不可能在mid和mid的左边
left = mid + 1
else:
# 由于循环退出条件是left <= right，所以最终返回的其实是一个[right+1, right]
# 也就是说我们允许right取到最终插入位置的左边一位，因为最终返回的是left:right+1
right = mid - 1
return left
最终返回的index，就是和target相等的元素的位置或第一次大于target的元素出现的位置，也就是我们最终想要插入的位点
Leetcode 35. Search Insert Position里面规定了所有的元素都是distinct的，但如果里面存在相同的元素呢？如果存在和target值相同的重复元素，如果我们希望插入在第一次该值出现的位置，那么就变成了一个lower bound问题
class Solution:
def searchInsert_lb(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) # 注意由于while条件的改变，这里改成了len(nums)
while left < right: # 这里的条件需要改动成left < right
mid = (left + right) // 2
# 删去了对nums[mid]==target的检查，因为nums[mid]不一定是该value的第一次出现
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
这里的返回条件是left == right , 最终 left 指向第一个 ≥ target 的元素
让我们再在上题的基础上进行一些改动，如果我们想把元素插入到最后一个跟target相同的元素出现的地方呢？
class Solution:
def searchInsert_ub(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return max(left - 1, 0)
这里会向右移动 left，直到所有 <= target 的元素都被排除
上面的三种情况都是用于binary search insert，但如果我们单纯想进行binary search这个行为呢
def binarySearch(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return -1
def binarySearch_lb(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
if left < len(nums) and nums[left] == target:
return target
return -1
def binarySearch_ub(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
if left > 0 and nums[left-1] == target:
return left-1
return -1