One of the most fundamental algorithms in computer science is the Binary Search algorithm. You can implement Binary Search using two methods: the iterative method and the recursive method. While both methods have the same time complexity, the iterative method is much more efficient in terms of space complexity.
The iterative method has a space complexity of O(1) as compared to O(logn) produced by the recursive method. So, how can you implement the Binary Search algorithm using the iterative method in C, C++, and Python?
What Is Binary Search?
Binary search also known as half-interval search, logarithmic search, or binary chop is an algorithm that searches and returns the position of an element in a sorted array. The search element is compared to the middle element. Taking the average of the lower and upper limits, you can find the middle elements.
If the search element is greater than the middle element, it means all the elements on the left side are smaller than the search element. So, the control shifts to the right side of the array (if the array is in ascending order) by increasing the lower limit to the next position of the middle element.
Similarly, if the search element is smaller than the middle element, it means all the elements on the right side are greater than the search element. So, the control shifts to the left part of the array by changing the upper limit to the previous position of the middle element.
This reduces the number of comparisons drastically as compared to linear search implementation where there the number of comparisons equals the number of elements in the worst-case scenario. This method proves very useful for finding numbers in a phonebook or words in a dictionary.
Here’s a diagrammatic representation of the Binary Search algorithm:
Binary Search Using C
Follow these steps to implement Binary Search using C:
The entire source code of the Binary Search Program using C, C++, Java, and Python is present in this GitHub repository.
The program defines a function, binarySearch(), that returns either the index of the found value or -1 if it’s not present:
int binarySearch(int arr, int arr_size, int search_number)
The function works by iteratively narrowing down the search space. Since binary search works on sorted arrays, you can calculate the middle which otherwise doesn’t make sense. You can either ask the user for a sorted array or use sorting algorithms such as Bubble or Selection sort.
The low and high variables store the indexes that represent the boundaries of the current search space. mid stores the index in the middle:
int low = 0, high = arr_size - 1, mid;
The main while() loop will narrow down the search space. If the value of the low index ever becomes greater than the high index, then the search space has been exhausted, so the value cannot be present.
while (low <= high)
After updating the midpoint at the beginning of the loop, there are three possible outcomes:
- If the value at the midpoint is the one we’re looking for, return that index.
- If the midpoint value is greater than the one we’re looking for, reduce the high.
- If the midpoint value is less, increase the low.
mid = (low + (high - low)) / 2;
if (arr[mid] == search_number)
else if (arr[mid] > search_number)
high = mid - 1;
low = mid + 1;
Test the function with user input. Use scanf() to get input from the command line, including the array size, its contents, and a number to search for:
int arr, i, arr_size, search_number;
printf("Enter number of elements: ");
printf("Please enter numbers: ");
for (i = 0; i < arr_size; i++)
printf("Enter number to be searched: ");
i = binarySearch(arr, arr_size, search_number);
printf("Number not present");
printf("Number is present at position %d", i + 1);
If you find the number, display its position or index, otherwise a message saying the number is not present.
Binary Search Using C++
You can convert the C program to a C++ program by importing the Input Output Stream and use namespace std to avoid repeating it multiple times throughout the program.
using namespace std;
Use cout with extraction operator << instead of printf() and cin with insertion operator >> instead of scanf() and your C++ program is ready.
printf("Enter number of elements: ");
cout << "Enter number of elements: ";
cin >> arr_size;
Binary Search Using Python
As Python does not have inbuilt support for arrays, use lists. Define a function, binarySearch(), that accepts three parameters, the list, its size, and a number to search for:
def binarySearch(arr, arr_size, search_number):
low = 0
high = arr_size - 1
while low <= high:
mid = low + (high-low)
if arr[mid] == search_number:
elif arr[mid] > search_number:
high = mid - 1
low = mid + 1
Initialize two variables, low and high, to serve as the lower and upper bound of the list. Similar to the C implementation, use a while loop that narrows down the search space. Initialize mid to store the middle value of the list. Python provides the floor division operator(//) that provides the largest possible integer.
Make the comparisons and narrow the search space until the mid value equals the search number. If the search number is not present, the control will return -1.
arr_size = int(input("Enter number of elements: "))
print("Please enter numbers: ", end=" ")
for i in range(0,arr_size):
search_number = int(input("Enter number to be searched: "))
result = binarySearch(arr, arr_size, search_number)
if result == -1:
print("Number not present")
print("Number is present at position ", (result + 1))
Test the function with user input. Use input() to get the list size, its contents, and a number to search for. Use int() to typecast the string input accepted by Python as default into an integer. To add numbers to the list, use the append() function.
Call binarySearch() and pass the arguments. If you find the number, display its position or index, otherwise a message saying the number is not present.
Output of Binary Search Algorithm
The following is the output of the Binary Search algorithm when the element is present in the array:
The following is the output of the Binary Search algorithm when the element is not present in the array:
Learn the Fundamental Data Structures and Algorithms
Searching is one of the first algorithms you learn and are often asked in coding contests, placements, and interviews. Some other algorithms you should learn are sorting, hashing, dynamic programming, string matching, and primality testing algorithms.
Additionally, it is essential to understand the time and space complexity of algorithms. They are one of the most crucial concepts in Computer Science in determining the efficiency of any algorithm. With knowledge of Data Structures and Algorithms, you are bound to build the best programs.