DEV Community

loading...

Divide and Conquer

Joseph Louie
Software Engineer
・1 min read

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
Enter fullscreen mode Exit fullscreen mode

Below shows how binary search would work with an odd number of elements in the list.
odd 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.

even list

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

Discussion (0)