Binary Search

 What is Binary Search?

Binary search is a search algorithm used to find the position of a target value within a sorted array. The algorithm works by repeatedly dividing the array in half and eliminating the half of the array that cannot contain the target element until the target element is found or the search ends with an empty subarray.

Here are the steps of the binary search algorithm:

Define the search range: Initialize two pointers, low and high, to the start and end of the array, respectively.

Find the middle element: Calculate the middle index of the array as the average of the low and high pointers.

Compare the target element with the middle element: If the target element matches the middle element, return the index of the middle element. If the target element is less than the middle element, discard the upper half of the array and repeat the search on the lower half. If the target element is greater than the middle element, discard the lower half of the array and repeat the search on the upper half.

Repeat steps 2-3 until the target element is found or the search range is empty.

Here is an example of the binary search algorithm in action:

Suppose we have the following sorted array:

[2, 5, 7, 8, 12, 16, 21, 23, 27, 31]

We want to find the position of the element 16.

Define the search range: low=0, high=9.

Find the middle element: middle=4 (integer division of (low+high)/2).

Compare the target element with the middle element: 16>12, discard the lower half of the array [2, 5, 7, 8, 12].

Define the new search range: low=middle+1=5, high=9.

Find the middle element: middle=7.

Compare the target element with the middle element: 16>23, discard the upper half of the array [21, 23, 27, 31].

Define the new search range: low=5, high=6.

Find the middle element: middle=5.

Compare the target element with the middle element: 16=16, return the index 5.

The binary search algorithm has a time complexity of O(log n) since the search range is divided in half at each step. This makes it a very efficient algorithm for large arrays compared to linear search, which has a time complexity of O(n). However, binary search requires a sorted array as input, which can be an additional cost if the array is not already sorted.

Binary Search implementation in python

Here's an 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  # Target not found

arr = [2, 5, 7, 8, 12, 16, 21, 23, 27, 31]

target = 16

print(binary_search(arr, target))  # Output: 5