Implementing a Binary Search Algorithm

Implementing a Binary Search Algorithm

Introduction

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

Step 1: Define the Problem

We are given a sorted array and a target element, and we need to find the index of the target element in the array.

Step 2: Initialize the Low and High Indices

We will initialize the low index to 0 and the high index to the last index of the array.

Step 3: Calculate the Mid Index

We will calculate the mid index using the formula mid = (low + high) // 2.

Step 4: Compare the Target Element with the Mid Element

We will compare the target element with the element at the mid index.

Step 5: Update the Low or High Index

If the target element is less than the mid element, we will update the high index to mid - 1. If the target element is greater than the mid element, we will update the low index to mid + 1.

Example Code

def binary_search(array, target):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = (low + high) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
print(binary_search([1, 2, 3, 4, 5], 3))  # Output: 2

Conclusion

In this tutorial, we learned how to implement a binary search algorithm to find an element in a sorted array.