# Binary Search

Use on a sorted collection to discard half of the collection with each iteration. This narrows the collection down to the target value if one exists. If the loop runs to completion then the target value is not in the collection.

Time complexity: O(log n)

Space complexity: O(1) for iterative algorithm. O(log n) for recursive algorithm.

def binary_search(nums: List[int], target: [int]) -> int | None:

left = 0

right = len(nums) - 1

# Less than or equal check is used in while condition to handle the case when there is one element

while left <= right:

# the middle (or average) of the range

mid = (right + left) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return None

Note:

- The
`mid = (right + left) // 2`

formula is fine for Python, where we don't need to worry about Integer overflow errors. In Java the formula should be`mid = left + (right - left) / 2`

. See Integer Overflow error in this article.

def binary_search_recursive(nums: List[int], target: [int]) -> int | None:

def recursive(left, right):

if left > right:

return None

mid = (left + right) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

return recursive(mid + 1, right)

else:

return recursive(left, mid - 1)

return recursive(0, len(nums) - 1)

Last modified 1yr ago