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 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

Variations and Use-Cases