Skip to content

Binary Search

Traditional binary search

  • Time complexity: O(log n) - The search space is halved with each iteration, leading to logarithmic time complexity.
  • Space complexity: O(1) - The algorithm uses a constant amount of space, as it only requires a few variables to keep track of the search range and the target value.
1
a = [-3, -1, 0, 1, 4, 7]

Binary search function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def binary_search(array, target):
    array_length = len(a)
    left_index = 0
    right_index = array_length - 1

    while left_index <= right_index:
        mean_index = left_index + (right_index - left_index) // 2

        if array[mean_index] == target:
            return True
        elif target < array[mean_index]:
            right_index = mean_index - 1
        else:
            left_index = mean_index + 1

    return False


binary_search(a, 7)

True