This article is the extension of the last article “Binary Search Algorithm” in which we have covered the basic idea around binary search and how its works along with two types of algorithms (Iterative and Recursive).
Binary Search Implementation and Time Complexity Analysis
In this article, you will learn the implementation of Binary search in different languages like Python, Java, and C++. You will also be able to understand the time complexity analysis of Binary Search.
Introduction
I hope by now you have a clear understanding of what is Binary Search and the internal working of binary search. You will now look at another example of binary to understand better and then we will implement it.
Let us consider the array of elements {2,5,8,12,16,23,38,56,72,91} and the search key/element is 23.
Now we find the mid values and check if the mid element is equal to 23. In the given array the mid value is 4 and the element at that position is 16 which is not equal to 23 so we compare 23 with 16 and it is greater so we move to the right side and repeat the process.
The next mid value is 56 which is greater than 23 so we move to the left side.
The mid value is 23 which is equal to the search element so the search is successful. We return the position of 23.
Now that we understood the algorithm completely let’s move to the coding part.
Iterative Implementation of Binary Search
Python
# Binary Search in python
def binarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
Java
// Binary Search in Java
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int array[] = { 3, 4, 5, 6, 7, 8, 9 };
int n = array.length;
int x = 4;
int result = ob.binarySearch(array, x, 0, n - 1);
if (result == -1)
System.out.println("Not found");
else
System.out.println("Element found at index " + result);
}
}
C++
// Binary Search in C++
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high) {
// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int x = 4;
int n = sizeof(array) / sizeof(array[0]);
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
}
Run the above codes and observe the output.
That’s it for this article. In the next article, we are going to have a look at Recursive implementation of binary search and the time complexity analysis.
