Binary Search Tree

Binary Search

Binary search is an efficient algorithm used to search for a target value within a sorted array or list. Here's an explanation of how the binary search algorithm works:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        # Check if target is found 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

    # If target is not found in array
    return -1

Explanation:

1. The binary search algorithm works on sorted arrays. It repeatedly divides the search interval in half until the target element is found or the interval is empty.
2. Initially, the search interval spans the entire array. We set two pointers, left and right, to the start and end indices of the array, respectively.
3. In each iteration of the while loop, we calculate the middle index of the current search interval using mid = (left + right) // 2.
4. We then compare the element at the middle index (arr[mid]) with the target value:
   • If they are equal, we have found the target, and we return the index mid.
   • If the element at mid is less than the target, we update left to mid + 1 to search in the right half of the array.
   • If the element at mid is greater than the target, we update right to mid - 1 to search in the left half of the array.
5. We continue this process until left is greater than right, indicating that the target is not found in the array.

Time Complexity:

The time complexity of binary search is \(O(\log n)\), where \(n\) is the size of the input array.

• In each iteration, the search interval is divided in half, effectively halving the search space.
• Therefore, the number of iterations required to find the target is proportional to the logarithm of the size of the array.
• This logarithmic growth rate is why binary search is highly efficient for searching in sorted arrays compared to linear search (\(O(n)\)).