Skip to content

Implementing Binary Search to Find Elements in Python Sorted Arrays

Updated: at 03:12 AM

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half, eliminating parts of the array that cannot contain the target element until it is found. Binary search is much faster than linear search, especially for large arrays, as it eliminates half of the remaining elements after each iteration. This article provides a comprehensive guide on implementing binary search in Python, examining the algorithm logic, code examples, complexity analysis, and variations.

Table of Contents

Open Table of Contents

Binary search follows the divide-and-conquer algorithm strategy to search for an element in an array. The key requirements are:

The basic steps are:

  1. Initialize the start and end index for the search space.

  2. Calculate the middle index as the average of the start and end indices.

  3. Compare the target value to the middle element.

  4. If it matches, return the middle index.

  5. Else if the target is less than the middle, make the end index equal to the middle - 1.

  6. Else if the target is greater than the middle, make the start index equal to the middle + 1.

  7. Repeat steps 2-6, successively narrowing the search space interval, until the target is found or the interval is empty.

  8. If the search space empties, return -1 to indicate the target is not found.

This halves the search space each iteration, providing a worst-case time complexity of O(log n).

Here is an implementation of binary search in Python:

def binary_search(arr, target):

  start = 0
  end = len(arr) - 1

  while start <= end:

    mid = (start + end) // 2

    if arr[mid] == target:
      return mid

    elif arr[mid] < target:
      start = mid + 1

    else:
      end = mid - 1

  return -1

To use this function:

arr = [1,5,23,111,144,500]
target = 144

result = binary_search(arr, target)

if result != -1:
  print("Element found at index", result)
else:
  print("Element not found")

This prints “Element found at index 4”, since 144 exists at index 4 in the array.

Handling Edge Cases

The basic implementation above does not handle edge cases properly. Here are some improvements:

1. Empty array: Check if the array is empty before searching and return -1 directly.

if len(arr) == 0:
  return -1

2. Out of bounds indices: Calculate the mid index using:

mid = start + (end - start) // 2

This avoids overflow when start and end are large.

3. Repeated elements: Return the leftmost index in case of duplicates.

while start < end:

  # Other code

  if arr[mid] == target:
    end = mid

return start

Complexity Analysis

Time Complexity:

As the search space is halved each iteration, binary search takes O(log n) time in the worst case, where n is the array size. The number of iterations before the space is reduced to 1 is log2(n).

Space Complexity:

The algorithm runs in O(1) constant space, as it only stores the start, end, mid indices and does not use any other data structure.

Optimizations and Variations

Here are some optimizations and variations of binary search:

Example Binary Search Code Snippets

Here are some examples demonstrating the optimizations and variations of binary search discussed above:

Recursive Implementation

def binary_search_recursive(arr, target, start, end):

  if start > end:
    return -1

  mid = (start + end) // 2

  if arr[mid] == target:
    return mid

  elif arr[mid] < target:
    return binary_search_recursive(arr, target, mid+1, end)

  else:
    return binary_search_recursive(arr, target, start, mid-1)

# Initial call
result = binary_search_recursive(arr, target, 0, len(arr)-1)

Search First Occurrence

def binary_search_first(arr, target):

  start = 0
  end = len(arr) - 1
  first_index = -1

  while start <= end:

    mid = (start + end) // 2

    if arr[mid] == target:
      first_index = mid
      end = mid - 1

    elif arr[mid] < target:
      start = mid + 1

    else:
      end = mid - 1

  return first_index

Binary Search on String Array

strings = ["apple", "mango", "orange", "pear"]
target = "mango"

# Lexicographically sort strings
strings.sort()

def binary_search_string(strings, target):

  # Implement string binary search

print(binary_search_string(strings, target))

Search Rotated Sorted Array

def search_rotated_array(arr, target):

  pivot = find_pivot(arr)

  # Search in first half
  if arr[pivot] <= target <= arr[len(arr)-1]:
    return binary_search(arr, target, 0, pivot)
  # Search in second half
  else:
    return binary_search(arr, target, pivot+1, len(arr)-1)

def find_pivot(arr):
  start = 0
  end = len(arr) - 1

  while start <= end:
    mid = (start + end) // 2
    if mid < end and arr[mid] > arr[mid + 1]:
      return mid
    elif mid > start and arr[mid] < arr[mid - 1]:
      return mid-1
    elif arr[start] >= arr[mid]:
      end = mid - 1
    else:
      start = mid + 1

These demonstrate how binary search can be adapted to different scenarios and use cases. The key ideas remain dividing the search space and progressively narrowing intervals.

Binary search is used extensively in various domains:

Searching Sorted Data: Arrays, lists, matrices, databases, files

Optimization Algorithms: Minimum/maximum finding, Golden section search

Resource Locations: Jump tables, memory addresses, pages, blocks, sectors

Data Compression: Dictionary-based like LZW, predictive coding

Signal Processing: Noise thresholding, step detection, pulse detection

Networking: MAC forwarding table lookups, IP lookups, port lookups

Graphics: Lighting calculation, anti-aliasing, ray tracing

Physics and Mathematics: Root finding, inequality solving, simulations

Games: Movement optimizations, pathfinding, terrain generation

Distributed Systems: Lookup services, source coding, redundancy removal

Machine Learning: Hyperparameter optimization, neural architecture search, clustering

Cryptography: Ciphertext searching, collision finding, identity testing

Bioinformatics: Genome alignment, protein sequencing, BLAST search

As a powerful algorithm at the core of computing, binary search enables efficiencies in virtually every technical field. Mastering implementations in Python is key for computer science and coding interviews.

Conclusion

Binary search is a fundamental algorithm that greatly speeds up searching in sorted arrays. This guide covered how it works, Python implementations, edge cases, optimizations, variations, code examples, complexity analysis, and applications. The key ideas are utilizing the sorted order to eliminate halves of the search space each iteration and recursively narrowing the interval till the target is found. With practice, binary search can be adapted to various use cases. Fluency in binary search coding questions demonstrates strong technical and analytical skills crucial for programming interviews and roles.