Binary Search Algorithm

Binary Search Algorithm

Binary search is an efficient algorithm for finding an element in a sorted list. It works by repeatedly dividing the search interval in half. If the target value is less than the midpoint, the search continues in the lower half, and if greater, in the upper half.

How Binary Search Works

1. Start with the entire list.
2. Find the middle element.
3. If the middle element is the target, return its index.
4. If the target is less than the middle element, repeat the search on the left half.
5. If the target is greater than the middle element, repeat the search on the right half.
6. Repeat steps 2-5 until the target is found or the interval is empty.

Pseudocode

Here is the pseudocode for a binary search algorithm:

BEGIN
    INPUT sorted_list, target
    SET low = 0
    SET high = length(sorted_list) - 1

    WHILE low <= high
        SET mid = (low + high) / 2
        IF sorted_list[mid] == target THEN
            RETURN mid
        ELSE IF sorted_list[mid] < target THEN
            SET low = mid + 1
        ELSE
            SET high = mid - 1
        ENDIF
    ENDWHILE

    RETURN -1  // Target not found
END

Example in Python

Below is an example implementation of binary search in Python:

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

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

    return -1

# Example usage
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search(numbers, target)

if result != -1:
    print("Element found at index "+str(result))
else:
    print("Element not found")

Key Points

Use Cases: Best suited for large, sorted lists.

Advantages

• Much more efficient than linear search for large datasets.
• Reduces the time complexity significantly compared to linear search.

Disadvantages

• Requires the list to be sorted.
• More complex to implement compared to linear search.

• Time Complexity: O(log n), where n is the number of elements in the list.
• Space Complexity: O(1), as it uses a constant amount of extra space.