Binary Search

Binary Search Algorithm

While sorting arrays is important, we usually sort data so that we can search it efficiently.

If you have an unsorted array, you have to use Linear Search (checking every item one by one). But if your array is sorted, you can use the much faster Binary Search.

1. How Does Binary Search Work?

Binary Search uses a Divide and Conquer strategy.

Because the array is already sorted, you can compare your target value directly to the middle element of the array:

1. If the target equals the middle element, you're done!
2. If the target is smaller than the middle element, you can safely ignore the entire right half of the array.
3. If the target is larger, you can ignore the entire left half.

You then repeat this process on the remaining half until you find the target or run out of elements to check.

Binary Search: Halving the search space with every step to find the target quickly.

2. A Step-by-Step Example

Let's search for the target 23 in the following sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Step 1:

• The array has 10 elements. The middle element is 16.
• Since 23 > 16, we know 23 must be on the right side.
• We ignore the entire left half: [2, 5, 8, 12, 16].

Step 2:

• Our new search space is the right half: [23, 38, 56, 72, 91].
• The middle element of this space is 56.
• Since 23 < 56, we know 23 must be on the left side of this section.
• We ignore [56, 72, 91].

Step 3:

• Our new search space is just [23, 38].
• The middle element is 23.
• We found our target!

3. Binary Search Code Example

Here is how you write Binary Search in Python. We use two pointers (left and right) to keep track of the portion of the array we are currently searching.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2  # Find the middle index
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target is greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
        # If target is smaller, ignore right half
        else:
            right = mid - 1
    # Target was not found
    return -1

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(numbers, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print("Element not found in array")

4. Time Complexity

• Time Complexity: O(log n). Because we cut the array in half every time, the number of steps required grows very slowly. For an array of 1,000,000 items, Binary Search takes at most 20 steps!
• Space Complexity: O(1). It only requires a few variables (left, right, mid) to execute, regardless of how large the array is.