AlgoBreath

Binary Search

Binary search is an efficient algorithm used to find a specific element in a sorted array or list. It works by repeatedly dividing the search interval in half, comparing the middle element with the target element, and discarding the half that cannot contain the target.

Here's how the binary search algorithm works:

  1. Begin with a sorted array or list of elements.
  2. Set two pointers, low and high, initially pointing to the first and last elements of the array, respectively.
  3. While low is less than or equal to high, do the following:
    • Calculate the middle index as mid = (low + high) / 2.
    • Compare the middle element arr[mid] with the target element target:
      • If arr[mid] is equal to target, the search is successful, and the algorithm returns the index mid.
      • If arr[mid] is greater than target, update high = mid - 1 to search in the lower half of the array.
      • If arr[mid] is less than target, update low = mid + 1 to search in the upper half of the array.
  4. If the target element is not found, the algorithm returns a sentinel value (e.g., -1) to indicate that the element is not present in the array.

The binary search algorithm has a time complexity of O(log n), where n is the number of elements in the array. This makes it much more efficient than a linear search, which has a time complexity of O(n).

Here's 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:
            high = mid - 1
        else:
            low = mid + 1

    return -1

In this implementation, the function takes a sorted array arr and a target element target as input. It returns the index of the target element if found, or -1 if the element is not present in the array.

Binary search is a fundamental algorithm used in many applications, such as searching in databases, finding elements in sorted collections, and optimizing various algorithms. It is important to note that the array or list must be sorted for binary search to work correctly.

PrevNext