Binary Search Algorithm

Binary search is a search algorithm that divides the sorted array or list in half with each iteration until the target value is found or the size of the interval becomes zero.

How Binary Search Works

1. Start with the middle element of the array.
2. If the middle element matches the target, return the index of the middle element.
3. If the target is less than the middle element, repeat the process on the left half of the array.
4. If the target is greater than the middle element, repeat the process on the right half of the array.
5. Repeat steps 1-4 until the target is found or the interval is empty.

Implementation

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

Complexity

The time complexity of binary search is O(log n), where n is the number of elements in the array.

Example

Let's say we have the following sorted array:

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

If we want to find the index of the number 11, we can use the binary search algorithm:

target = 11
index = binary_search(arr, target)
print("Index of", target, "is", index)

The output will be:

Index of 11 is 5

For more information on binary search and related algorithms, check out our algorithm tutorials.

[center]