The mother of all divide-and-conquer algorithms is binary search, which is a fast algorithm for searching in a sorted array of keys .
To search for key , we compare to the middle key .
- If appears before it must reside in the left half of
- If not, it must reside in the right half of S.
- By repeating this process recursively on the correct half, we locate the key in a total of comparisons — a big win over the n/2 comparisons expected using sequential search.
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = l + ((r-l) // 2)
if nums[m] > target:
r = m - 1
elif nums[m] < target:
l = m + 1
elif nums[m] == target:
return m
return -1