Binary Search Algorithm: Pseudocode and Explanation

In the previous article, we explored the logic and intuition behind binary search and visualized how it works. Now, let’s dive deeper into the algorithmic details, including the roles of low, mid, and high pointers. We’ll also provide pseudocode for both iterative and recursive approaches. By the end of this article, you’ll have a clear understanding of how to implement binary search in code.

Prerequisites:

Terminologies used in the Binary Search Algorithm

Before we dive deeper into the binary search algorithm, let’s clarify some key terms:

  • Sorted List:

    • A sorted list is a collection of elements arranged in a specific order (usually ascending or descending or alphabetical order).
    • Examples:
      • [1, 3, 5, 7, 9, 11] is sorted list in ascending order.
      • ['apple', 'banana', 'cherry', 'date', 'fig'] is a sorted list in alphabetical order.
      • [100, 85, 70, 55, 40, 25] is a sorted list in descending order.
    • Binary search requires a sorted list to work correctly.

  • Target Element:

    • The value we’re trying to find in the sorted list.

  • Search Area/Space:

    • The portion of the list where the target might be present.
    • Initially, the search space is the entire list.
    • The binary search algorithm reduces the search space by half with each iteration.

  • Comparison:

    • The act of checking if the middle element is equal to, greater than, or less than the target.
    • This determines which half of the current search area to search next.

  • Halving:

    • The process of dividing the search area into two equal (or nearly equal) parts.
    • This is the key to binary search’s efficiency.

  • Index:

    • The position of an element in the list, starting from 0.
    • Used to access elements and track the search boundaries.

Understanding these terms will help you grasp the binary search algorithm more easily as we explore its implementation and mechanics.

Understanding the Pointers

Before we look at the implementations, let’s understand the three critical pointers used in binary search:

  1. Low Pointer (left)

    • Marks the start of the current search area
    • Initially set to index 0

  2. High Pointer (right)

    • Marks the end of the current search area
    • Initially set to the last index of the list: (length - 1)

  3. Middle Pointer (mid)

    • Calculated as (low + high) // 2
    • Divides current search space into two halves
    • Used for comparison with target element

Note: For finding the middle pointer, the expression(low + high) // 2 is used instead of (low + high) / 2 as we require only the integer part of the division. For example, if low is 5 and high is 6, (5 + 6) / 2 would give 5.5, but we need an integer index. The // operator in many programming languages (like Python) performs integer division, so (5 + 6) // 2 gives 5, which is a valid index. This ensures that we always have a whole number for our mid index, which is crucial when accessing array elements.

Iterative Binary Search Algorithm

Algorithm

  1. Initialize Pointers:

    • Initialise two variables low and high.
    • Set low to the first index (0) of the array.
      • low pointer represents the starting index of the current search area in the sorted list.
    • Set high to the last index (length - 1) of the array.
      • high pointer represents the ending index of the current search area in the sorted list.

  2. Enter Loop:

    • Continue the steps 3 and 4 while low pointer is less than or equal to high pointer.
      • This ensures we have stop iterating when the current search area is reduced to 0.

  3. Calculate Middle:

    • Compute mid pointer as (low+high) // 2.
      • mid represents the middle index of the current search space.
      • The mid index contains the the element we’ll compare with our target.

  4. Compare and Decide:

    • If arr[mid] equals the target (arr is the array or sorted list):
      • Return mid (index of the target element).
      • (mid is the index corresponding to the target element in the sorted list).
    • If arr[mid] is less than the target:
      • Update low = mid + 1 (search right half).
      • This reduces the current search area to the right half.
      • Example scenario:
    • If arr[mid] is greater than the target:
      • Update high = mid - 1 (search left half).
      • This reduces the current search area to the left half.
      • Example scenario:

  5. Repeat or Exit:

    • Go back to step 2 if the loop condition is still true.
      • This means we still have a valid search space to explore.
    • If the loop ends without finding the target, return -1 (which indicates that the element is not found).
      • This happens when low becomes greater than high, indicating that the size of current search area is reduced to 0.

Throughout this process, low and high continuously adjust to narrow down the search space, while mid helps us make decisions about which half of the current search space to ignore and which half of the current search space to search next.

Visualization

Pseudocode

Here’s the pseudocode for the iterative approach of binary search algorithm:


def binary_search_iterative(arr, target):
  # Initialize the pointers
  low = 0
  high = len(arr) - 1
  
  # Continue while there's a valid search space
  while low <= high:
    # Calculate middle point
    # Note: (low + high) // 2 can cause integer overflow
    mid = low + (high - low) // 2
    
    # Case 1: Element found
    if arr[mid] == target:
      return mid
      
    # Case 2: Target is in right half
    elif arr[mid] < target:
      # Move low pointer to exclude left half
      low = mid + 1
      
    # Case 3: Target is in left half
    else:
      # Move high pointer to exclude right half
      high = mid - 1
  
  # Element not found
  return -1

If the target element is present in the given array/list, the function binary_search_iterative returns the index of the target element. Otherwise it returns -1 indicating that the target element is not present in the list.

Note: We use mid = low + (high - low) // 2 instead of mid = (high + low) // 2 to avoid potential integer overflow. When high and low are very large integers, their sum could exceed the maximum value that can be stored in an integer variable, causing an overflow. By using low + (high - low) // 2, we ensure that the calculation stays within the range of integer values, making the algorithm more robust and less prone to errors in extreme cases.

Example Walkthrough

Let’s walk through the iterative binary search algorithm using the array [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] and searching for the target value 14:

  1. Initialization:

    • low = 0, high = 9, target = 14
    • low is set to 0 because it represents the index of the first element in the array.
    • high is set to 9 because it represents the index of the last element in the array. Since array indexing starts at 0 and our array has 10 elements, the last index is 9 (length - 1)
    • This means that the current search area spans from low (0) to high (9) indexes:
    • 0
      0
      1
      1
      2
      2
      3
      3
      4
      4
      5
      5
      6
      6
      7
      7
      8
      8
      9
      9
      2
      2
      4
      4
      6
      6
      8
      8
      10
      10
      12
      12
      14
      14
      16
      16
      18
      18
      20
      20
      low
      low
      high
      high      Text is not SVG - cannot display
    • target is the value we’re searching for in the array.

  2. First Iteration:

    • mid = low + (high - low) // 2
    • mid = 0 + (9 - 0) // 2 = 4
    • arr[mid] = arr[4] = 10
    • 10 < 14, so we search the right half
    • Update low = mid + 1 = 5 which makes the current search area to the subportion of array between index low (5) and high (9):
    • 0
      0
      1
      1
      2
      2
      3
      3
      4
      4
      5
      5
      6
      6
      7
      7
      8
      8
      9
      9
      2
      2
      4
      4
      6
      6
      8
      8
      10
      10
      12
      12
      14
      14
      16
      16
      18
      18
      20
      20
      low
      low
      high
      high      Text is not SVG - cannot display

  3. Second Iteration:

    • low = 5, high = 9
    • mid = 5 + (9 - 5) // 2 = 7
    • arr[mid] = arr[7] = 16
    • 16 > 14, so we search the left half
    • Update high = mid - 1 = 6 which makes the current search area to the subportion of array between index low (5) and high (6):
    • 0
      0
      1
      1
      2
      2
      3
      3
      4
      4
      5
      5
      6
      6
      7
      7
      8
      8
      9
      9
      2
      2
      4
      4
      6
      6
      8
      8
      10
      10
      12
      12
      14
      14
      16
      16
      18
      18
      20
      20
      low
      low
      high
      high
      0
      0
      1
      1
      2
      2
      3
      3
      4
      4
      5
      5
      6
      6
      7
      7
      8
      8
      9
      9
      2
      2
      4
      4
      6
      6
      8
      8
      10
      10
      12
      12
      14
      14
      16
      16
      18
      18
      20
      20
      low
      low
      high
      high      Text is not SVG - cannot display

  4. Third Iteration:

    • low = 5, high = 6
    • mid = 5 + (6 - 5) // 2 = 5
    • arr[mid] = arr[5] = 12
    • 12 < 14, so we search the right half
    • Update low = mid + 1 = 6 which makes the current search area to the subportion of array between index low (6) and high (6):
    • 0
      0
      1
      1
      2
      2
      3
      3
      4
      4
      5
      5
      6
      6
      7
      7
      8
      8
      9
      9
      2
      2
      4
      4
      6
      6
      8
      8
      10
      10
      12
      12
      14
      14
      16
      16
      18
      18
      20
      20
      low
      low
      high
      high      Text is not SVG - cannot display

  5. Fourth Iteration:

    • low = 6, high = 6
    • mid = 6 + (6 - 6) // 2 = 6
    • arr[mid] = arr[6] = 14
    • 14 == 14, target found!
    • Return mid, which is 6

The algorithm terminates here, having found the target value 14 at index 6.

This example demonstrates how the iterative approach continually narrows down the search space until the target is found or the search space is exhausted. The low and high pointers adjust in each iteration to focus on the relevant half of the remaining search space.

Recursive Binary Search Algorithm

Algorithm

  1. Define the Function:

    • Create a recursive function that takes the array, target, low, and high as parameters

  2. Base Case: Element Not Found

    • If low is greater than high, return -1
    • This indicates the search space is empty

  3. Calculate Middle Index:

    • Compute mid as low + (high - low) // 2
    • This avoids potential integer overflow

  4. Base Case: Element Found

    • If arr[mid] equals the target, return mid
    • We’ve found the element, so we’re done

  5. Recursive Case: Search Right Half

    • If arr[mid] is less than the target:
      • Return the result of a recursive call with low = mid + 1
      • This narrows the search to the right half

  6. Recursive Case: Search Left Half

    • If arr[mid] is greater than the target:
      • Return the result of a recursive call with high = mid - 1
      • This narrows the search to the left half

  7. Wrapper Function (Optional):

    • Create a wrapper function that initializes low and high
    • This simplifies the function call for the user

The recursive approach follows the same logic as the iterative version, but instead of using a loop, it uses function calls to explore different parts of the array. Each recursive call works on a smaller portion of the array, effectively dividing the search space in half each time.

Visualization

Pseudocode

Here’s the pseudocode for the recursive approach of binary search algorithm:


def binary_search_recursive(arr, target, low, high):
  # Base case 1: Element not found
  if low > high:
    return -1
    
  # Calculate middle point
  mid = low + (high - low) // 2
  
  # Base case 2: Element found
  if arr[mid] == target:
    return mid
    
  # Recursive case 1: Search right half
  elif arr[mid] < target:
    return binary_search_recursive(arr, target, mid + 1, high)
    
  # Recursive case 2: Search left half
  else:
    return binary_search_recursive(arr, target, low, mid - 1)

# Wrapper function for easier usage
def binary_search(arr, target):
  return binary_search_recursive(arr, target, 0, len(arr) - 1)

Example Walkthrough

Let’s walk through the recursive binary search algorithm using the array [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] and searching for the target value 14:

  1. Initial Call: binary_search_recursive(arr, 14, 0, 9)

    • low = 0, high = 9
    • mid = 0 + (9 - 0) // 2 = 4
    • arr[4] = 10 (10 < 14)
    • Recurse on right half: binary_search_recursive(arr, 14, 5, 9)

  2. Second Call: binary_search_recursive(arr, 14, 5, 9)

    • low = 5, high = 9
    • mid = 5 + (9 - 5) // 2 = 7
    • arr[7] = 16 (16 > 14)
    • Recurse on left half: binary_search_recursive(arr, 14, 5, 6)

  3. Third Call: binary_search_recursive(arr, 14, 5, 6)

    • low = 5, high = 6
    • mid = 5 + (6 - 5) // 2 = 5
    • arr[5] = 12 (12 < 14)
    • Recurse on right half: binary_search_recursive(arr, 14, 6, 6)

  4. Fourth Call: binary_search_recursive(arr, 14, 6, 6)

    • low = 6, high = 6
    • mid = 6 + (6 - 6) // 2 = 6
    • arr[6] = 14 (14 == 14)
    • Target found! Return 6

The recursive calls end here, and the index 6 is returned through the call stack as the final result.

This example demonstrates how the recursive approach continually narrows down the search space until the target is found or the search space is exhausted. Each recursive call works on a smaller portion of the array, effectively dividing the search space in half each time.

Choosing Between Approaches

  1. Use the iterative approach of binary search algorithm When:

    • Memory is a concern
    • Maximum performance is needed
    • Code simplicity isn’t the primary concern

  2. Use the recursive approach of binary search algorithm When:

    • Code readability is priority
    • Stack space isn’t a concern
    • Problem naturally fits recursive thinking

What’s Next?

Now that you understand the binary search algorithm and its pseudocode, it’s time to implement it in real code! In the next article, we’ll walk through implementing binary search algorithm in various programming languages: