Python Practice: Implement a Binary Search Algorithm

Table of Contents

  1. Introduction
  2. Prerequisites
  3. Binary Search Algorithm
  4. Conclusion

Introduction

In this tutorial, we will learn how to implement a binary search algorithm in Python. Binary search is an efficient searching technique used to find the position of a target value within a sorted array. By the end of this tutorial, you will have a clear understanding of how binary search works and how to apply it in your own Python programs.

Prerequisites

To follow along with this tutorial, you should have a basic understanding of the Python programming language and familiarity with arrays or lists. It is also helpful to understand the concept of sorting data.

Binary Search Algorithm

Overview

Binary search is a divide-and-conquer algorithm that repeatedly divides the search space in half by comparing the target value with the middle element of the array. This process continues until the target value is found or the search space is empty.

  1. Start with a sorted array.
  2. Set the lower bound low to the first index of the array.
  3. Set the upper bound high to the last index of the array.
  4. Calculate the middle index mid as (low + high) // 2.
  5. Compare the target value with the element at index mid:
    • If the target value is equal to the element at mid, return mid.
    • If the target value is less than the element at mid, update high to mid - 1.
    • If the target value is greater than the element at mid, update low to mid + 1.
  6. Repeat steps 4-5 until the target value is found or the search space is empty.

Implementation

Let’s implement the binary search algorithm in Python: ```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
``` In the code above, we define a function `binary_search` that takes an array `arr` and a target value `target` as parameters. We initialize the lower bound `low` to the first index of the array and the upper bound `high` to the last index of the array. Then, we enter a `while` loop that continues until the lower bound becomes greater than the upper bound. Inside the loop, we calculate the middle index `mid` using integer division. We compare the target value with the element at index `mid` and update `low` or `high` accordingly. If the target value is found, we return the index `mid`. Otherwise, we return -1 to indicate that the target value is not present in the array.

Example Usage

Let’s see the binary search algorithm in action with some examples: ```python # Example 1 arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] target = 23 result = binary_search(arr, target) print(f”Target value {target} found at index {result}” if result != -1 else “Target value not found”)

# Example 2
arr = [3, 6, 9, 15, 21, 28, 34, 42, 50]
target = 11
result = binary_search(arr, target)
print(f"Target value {target} found at index {result}" if result != -1 else "Target value not found")
``` Output:
```
Target value 23 found at index 5
Target value not found
``` In the first example, we have an array `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]` and the target value is 23. We call the `binary_search` function with these inputs and it returns the index 5, indicating that the target value is found at that index.

In the second example, we have an array [3, 6, 9, 15, 21, 28, 34, 42, 50] and the target value is 11. The binary_search function returns -1, indicating that the target value is not present in the array.

Conclusion

In this tutorial, we learned how to implement a binary search algorithm in Python. We started with an overview of binary search and its steps. Then, we implemented the algorithm and demonstrated its usage with examples. Binary search is an efficient searching technique that can greatly improve the performance of searching for a target value in a sorted array. Keep practicing and applying this algorithm to solve various search problems efficiently.

Published:

Related Articles