Divide and Conquer

Divide and Conquer is a popular algorithm technique normally used on an array/list. The idea is to divide the list in half until you find your target or left <= right condition is not met. This reference will mainly be for reference for those who don't remember how binary search works.

def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = left + ((right - left) // 2)

    if nums[mid] == target:
      return mid

    if target < nums[mid]:
      right = mid - 1
    else:
      left = mid + 1
  return -1

Below shows how binary search would work with an odd number of elements in the list.

Below shows how binary search would work with an even number of elements in the list.

Note: With an even number of elements we pick the left element instead of the right.

Thank You for reading! I'm hoping to do this for more algorithm patterns.