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 the Recursive Implementation of Binary Search.
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.
Recursive Implementation of Binary Search
Python
# Binary Search in python
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if array[mid] == x:
return mid
# Search the left half
elif array[mid] > x:
return binarySearch(array, x, low, mid-1)
# Search the right half
else:
return binarySearch(array, x, mid + 1, high)
else:
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) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (array[mid] == x)
return mid;
// Search the left half
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// Search the right half
return binarySearch(array, x, mid + 1, high);
}
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) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (array[mid] == x)
return mid;
// Search the left half
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// Search the right half
return binarySearch(array, x, mid + 1, high);
}
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);
}
Time and Space Complexity Analysis
The time complexity of binary search can be analyzed using the number of comparisons required to find the target item. Each comparison reduces the size of the search space in half, so the number of comparisons required to find the target item is proportional to the logarithm of the size of the list.
The logarithm function is a mathematical function that grows much more slowly than the size of the input. For example, the logarithm of 10^6 (1 million) is just 20. So, even though the size of the list can be very large, the number of comparisons required to find the target item is small.
In mathematical terms, the time complexity of binary search can be expressed as O(log n), where n is the size of the list. This means that the number of comparisons required to find the target item grows logarithmically with the size of the list.
The Best Time Complexity of Binary Search is O(1) when the search element is the middle of the list.
The Worst time complexity of binary search is O(logN) when the search element is the first element or the last element in the list or in some cases it is not present in the list.
The space complexity of binary search is O(1), it requires a constant amount of additional memory space. This is because binary search only requires a few variables to keep track of the search space, such as the start and end indices of the current search interval, and the middle index calculated in each iteration.
That is all for this article, Happy Learning!
