Introduction to Binary Search

What is Binary Search?

Binary search is an efficient algorithm used to find a specific element in a sorted array or list. It works by repeatedly dividing the search space in half until the target element is found or determined to be absent.

How does Binary Search work?

Binary search starts by comparing the target element with the middle element of the array. If they are equal, the search is complete. If the target element is smaller, the search continues on the lower half of the array; otherwise, it continues on the upper half.

This process is repeated until the target element is found or the search space is empty.

Pros and Cons of Binary Search

Pros

• Efficient searching algorithm
• Divides the search space in half with each comparison
• Requires a sorted array, ensuring data integrity
• Can quickly find a desired element in a large data set

Cons

• Requires a sorted array, making initial setup time-consuming
• Not suitable for dynamic data sets that frequently change
• Cannot handle unsorted or unordered data
• Implementation is more complex than a linear search

Binary Search Python Implementation

Here is an example of Binary search python script. This script uses recursion, because the search function calls itself.

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

# Example usage
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search(array, target)

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