Implementing Binary Search

Implementing Binary Search

Introduction

This tutorial will guide you through implementing the 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 value, and we need to find the index of the target value in the array.

Step 2: Initialize the Low and High Pointers

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

Step 3: Calculate the Mid Index

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

Step 4: Compare the Mid Element with the Target Value

We will compare the mid element with the target value and update the low and high pointers accordingly.

Step 5: Repeat Steps 3 and 4 Until the Target Value is Found

We will repeat steps 3 and 4 until the target value is found or the low pointer is greater than the high pointer.

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 the binary search algorithm to find an element in a sorted array.