Implementation of Binary Search Algorithm in Python

In the previous article, we explored the binary search algorithm and wrote pseudocode for both iterative and recursive approaches. Now, it’s time to bring that pseudocode to life by implementing binary search in Python. By the end of this article, you’ll have a working implementation of binary search and a clear understanding of how to use it in your programs.

Prerequisites:

• Introduction to binary search for beginners
• Binary Search Algorithm: Step-by-Step Explanation and Visualization
• Binary Search Algorithm: Pseudocode and Explanation

Iterative Implementation of Binary Search in Python

Here’s the Python code for the iterative implementation of binary search algorithm:

Explanation

1. Initialization: Start with low at the beginning of the list and high at the end.
2. Loop: Continue searching as long as low is less than or equal to high.
3. Middle Element: Calculate mid and compare arr[mid] with the target.
4. Update Pointers: Adjust low or high based on the comparison.
5. Return: If the target is found, return its index. Otherwise, return -1.

Example Usage

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Target found at index {result}.")
else:
    print("Target not found.")

Output: Target found at index 5.

Recursive Implementation of Binary Search in Python

Here’s the Python code for the recursive implementation of binary search algorithm:

Explanation

1. Base Case: If low exceeds high, the target is not in the list.
2. Middle Element: Calculate mid and compare arr[mid] with the target.
3. Recursive Calls:
   • If the target is greater than arr[mid], search the right half of current search space.
   • If the target is less than arr[mid], search the left half of current search space.
4. Return: If the target is found, return its index. Otherwise, propagate the -1 from the base case.

Example Usage

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search_recursive(arr, target, 0, len(arr) - 1)
if result != -1:
    print(f"Target found at index {result}.")
else:
    print("Target not found.")

Output:
Target found at index 5.

Binary Search for Descending Order Lists

So far, we’ve implemented binary search for lists sorted in ascending order. But what if our list is sorted in descending order? Let’s explore the changes we need to make to our binary search implementations to handle this case.

Changes in the Algorithm

The core logic of binary search remains the same, but we need to adjust our comparisons:

1. When arr[mid] < target, we now search the left half (instead of right).
2. When arr[mid] > target, we now search the right half (instead of left).

Iterative Implementation for Descending Order

Here’s how we can modify our iterative implementation:

def binary_search_iterative_desc(arr, target):
  low, high = 0, len(arr) - 1
  
  while low <= high:
    mid = (low + high) // 2
    
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      high = mid - 1  # Search left half
    else:
      low = mid + 1   # Search right half
  
  return -1

Recursive Implementation for Descending Order

Similarly, we can adjust our recursive implementation:

def binary_search_recursive_desc(arr, target, low, high):
  if low > high:
    return -1
  
  mid = (low + high) // 2
  
  if arr[mid] == target:
    return mid
  elif arr[mid] < target:
    return binary_search_recursive_desc(arr, target, low, mid - 1)
  else:
    return binary_search_recursive_desc(arr, target, mid + 1, high)

Example Usage

arr_desc = [91, 72, 56, 38, 23, 16, 12, 8, 5, 2]
target = 23

result = binary_search_iterative_desc(arr_desc, target)
if result != -1:
  print(f"Target found at index {result}.")
else:
  print("Target not found.")

Output:
Target found at index 4.