How do you perform a binary search in a sorted array?

Binary search is one of the fastest searching algorithms, with a time complexity of O(log n). It works by repeatedly dividing the search interval in half. The algorithm works only on sorted arrays.

Here’s a step by step guide on how it’s implemented:

1. Find the middle element of the array. If the array has an even number of elements, the middle element is calculated as ‘mid = low + (high - low) / 2‘ where high is the index of the last element and low is the index of the first element (often 0). This method is more effective than ‘(low + high) / 2‘ as it avoids integer overflow for large values of low and high.

2. Compare the middle element with the target value. If the target value matches the middle element, return the middle index.

3. If the target value is less than the middle element, repeat the search with the left half of the array.

4. If the target value is greater than the middle element, repeat the search with the right half of the array.

5. Repeat step 1 to 4 until the target value is found or the search interval is empty.

Here is a Python example code for binary search:

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

    while low <= high:
        mid = low + (high - low) // 2

        if array[mid] == target:
            return mid
        elif array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Element is not present in the array

For instance, if you have a sorted array of ‘[1, 3, 5, 7, 9]‘ and you’re searching for ‘3‘, the function ‘binary_search([1, 3, 5, 7, 9], 3)‘ will return ‘1‘ which is the index of ‘3‘ in the given array.

Please note, the binary search algorithm is a divide and conquer algorithm, in each step, it reduces the search space by half. As a result, the time complexity of binary search is logarithmic.