Bellgigs
Bridging Skills and Opportunities

Binary Search is an efficient algorithm used to find a target element in a sorted array by repeatedly dividing the search interval in half. It has a time complexity of O(log n).

The array or list must be sorted (either ascending or descending). Binary Search will not work correctly on unsorted data.

The algorithm compares the middle element with the target value. If the target is smaller, it searches the left half; otherwise, it searches the right half, repeating this until the element is found or the search space is empty.

The time complexity is O(log n) because the search space is halved after each iteration. The best case is O(1) when the middle element is the target.

The space complexity is O(1) for the iterative version and O(log n) for the recursive version due to the call stack.

Binary Search is inefficient for linked lists because random access is not possible. Finding the middle element in a linked list requires linear time, making it less practical.

Advantages include

• Fast search performance on large datasets
• Simple implementation
• Predictable logarithmic time complexity

Disadvantages include

• Requires sorted data
• Not suitable for frequently changing datasets
• Inefficient for linked lists or unsorted collections

If the array is unsorted, Binary Search may produce incorrect results because it assumes a specific ordering of elements to decide which half to search.

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

Linear Search checks each element sequentially with O(n) time, while Binary Search divides the array and eliminates half the search space each time with O(log n) time.

Yes, Binary Search can work on descending sorted arrays by reversing the comparison logic (searching left when the target is greater than the middle element).

The worst-case scenario occurs when the element is not present or is found after maximum iterations, requiring O(log n) comparisons.

Applications include:

• Searching in sorted arrays
• Finding square roots
• Determining rotation count in rotated arrays
• Search in dictionaries and databases

When duplicates exist, modifications can be made to find the first or last occurrence by continuing the search after finding the target.

The search terminates when low > high, meaning the target element is not found in the given array.

Yes, by using an exponential search approach — first find the range where the element could exist, then perform binary search within that range.

Binary Search performs significantly faster (O(log n)) than Linear Search (O(n)), especially on large sorted datasets.