Implementation of Binary Search Algorithm in C and CPP

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 C. 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.

The same code is applicable for C++ as well, where instead of arrays, you can also use vectors. The logic and structure remain the same, with minor syntax differences.

Prerequisites:

Iterative Implementation of Binary Search in C

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


#include <stdio.h>

int binary_search_iterative(int arr[], int n, int target) {
  int low = 0;           // First index
  int high = n - 1;      // Last index

  // Keep searching while we have a valid search space
  while (low <= high) {
    // Find the middle element
    int mid = low + (high - low) / 2;
    
    // Check if we found the target
    if (arr[mid] == target) {
      return mid;  // Target found! Return its index
    }
    
    // If not found, eliminate half the search space
    else if (arr[mid] < target) {
      // Target is larger, ignore left half
      low = mid + 1;
    } else {
      // Target is smaller, ignore right half
      high = mid - 1;
    }
  }
  
  // If we get here, target wasn't found
  return -1;
}

Note: The variable n represents the size of the array arr[]. In C++, if you’re using a vector (which is a dynamic array), you don’t need to pass n separately because the vector already knows its size.

Explanation

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

Example Usage

#include <stdio.h>

int main() {
  int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 23;

  int result = binary_search_iterative(arr, n, target);
  if (result != -1) {
    printf("Target found at index %d.\n", result);
  } else {
    printf("Target not found.\n");
  }

  return 0;
}

Output: Target found at index 5.

Recursive Implementation of Binary Search in C

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


#include <stdio.h>

int binary_search_recursive(int arr[], int target, int low, int high) {
  // Base case 1: There is no search space left
  // Which means the target element is not found
  if (low > high) {
    return -1;
  }
  
  // Find middle point
  int mid = low + (high - low) / 2;
  
  // Base case 2: Found the target!
  if (arr[mid] == target) {
    return mid;
  }
  
  // Recursive case 1: Search right half
  if (arr[mid] < target) {
    return binary_search_recursive(arr, target, mid + 1, high);
  }
  
  // Recursive case 2: Search left half
  return binary_search_recursive(arr, target, low, mid - 1);
}

// Helper function to make it easier to use
int binary_search(int arr[], int n, int target) {
  return binary_search_recursive(arr, target, 0, n - 1);
}

Explanation

Base Case: If low exceeds high, the target is not in the array.
Middle Element: Calculate mid and compare arr[mid] with the target.
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.
Return: If the target is found, return its index. Otherwise, propagate the -1 from the base case.

Example Usage

#include <stdio.h>

int main() {
  int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 23;

  int result = binary_search(arr, n, target);
  if (result != -1) {
    printf("Target found at index %d.\n", result);
  } else {
    printf("Target not found.\n");
  }

  return 0;
}

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:

When arr[mid] < target, we now search the left half (instead of right).
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 for descending order lists:

int binary_search_iterative_desc(int arr[], int n, int target) {
  int low = 0, high = n - 1;
  
  while (low <= high) {
    int mid = low + (high - low) / 2;
    
    if (arr[mid] == target) {
      return mid;
    } else if (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:

int binary_search_recursive_desc(int arr[], int target, int low, int high) {
  if (low > high) {
    return -1;
  }
  
  int mid = low + (high - low) / 2;
  
  if (arr[mid] == target) {
    return mid;
  } else if (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

#include <stdio.h>

int main() {
  int arr_desc[] = {91, 72, 56, 38, 23, 16, 12, 8, 5, 2};
  int n = sizeof(arr_desc) / sizeof(arr_desc[0]);
  int target = 23;

  int result = binary_search_iterative_desc(arr_desc, n, target);
  if (result != -1) {
    printf("Target found at index %d.\n", result);
  } else {
    printf("Target not found.\n");
  }

  return 0;
}

Output:
Target found at index 4.