Binary search is a search algorithm that divides the sorted array or list in half with each iteration until the target value is found or the size of the interval becomes zero.

Key Points

  • Divide and Conquer: The algorithm divides the list into two halves and compares the middle element with the target value.
  • Sorted List: Binary search works only on a sorted list.
  • Time Complexity: The time complexity of binary search is O(log n).

Steps

  1. Start with the middle element of the list.
  2. If the middle element is equal to the target, return the index of the middle element.
  3. If the target is less than the middle element, search the left half of the list.
  4. If the target is greater than the middle element, search the right half of the list.
  5. Repeat steps 1-4 until the target is found or the size of the interval becomes zero.

Example

Let's say we have the following sorted list: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]. We want to find the index of the number 7.

  1. The middle element is 9. Since 7 is less than 9, we search the left half of the list.
  2. The new middle element is 5. Since 7 is greater than 5, we search the right half of the list.
  3. The new middle element is 7. We found the target value!

Implementation

Here is a simple implementation of binary search in Python:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Further Reading

For more information on binary search, you can visit the Wikipedia page on Binary Search.

Return to the Home Page