Implementing a Simple Binary Search Algorithm

Introduction to Binary Search

This tutorial will guide you through implementing a simple binary search algorithm to find an element in a sorted array.

Step 1: Define the Problem and the Approach

We are given a sorted array and a target element, and we need to find the index of the target element in the array. We will use a divide-and-conquer approach to solve this problem.

Step 2: Initialize the Low and High Indices

We will initialize the low and high indices to the start and end of the array, respectively.

low = 0
high = len(array) - 1

Step 3: Loop Until the Low Index is Less Than or Equal to the High Index

We will loop until the low index is less than or equal to the high index. In each iteration, we will calculate the mid index and compare the middle element to the target element.

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

Step 4: Return the Index of the Target Element

If the loop ends without finding the target element, we will return -1 to indicate that the element is not in the array.

return -1

Example Use Case

Here's an example use case:

array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
low = 0
high = len(array) - 1
while low <= high:
    mid = (low + high) // 2
    if array[mid] == target:
        print(mid)  # Output: 5
        break
    elif array[mid] < target:
        low = mid + 1
    else:
        high = mid - 1