Binary Search in Data Structure

Binary Search is a searching algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search range in half.

Algorithm Steps

• Compare the target with the middle element of the array.
• If they match, the search is complete.
• If the target is smaller, repeat the search on the left half.
• If the target is larger, repeat the search on the right half.
• Repeat until the target is found or the search range is empty.

def binary_search(arr, target):
    low, high = 0, 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

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

Complexity

Applications

• Searching in sorted databases and indexes.
• Finding the boundary in problems like 'first/last occurrence' or 'search in rotated sorted array'.
• Used in library functions like Python's bisect module.