Binary search is very fast and efficient searching algorithm.
It requires to be list be in a sorted order, ie; either in ascending or descending.In this method, to search an element you might compare that respective element present in the center of the list and if it’s same then the search is successfully finished and if not, then the list is divided into two parts:one from 0th element to the centered element and other from the centered element to the last element.
Step 1- Take a sorted array (mandatory)
Step 2- Find mid using formula m = (l+r)/2
Step 3- f the item to be searched is greater than mid
Step 4- If the item to be searched is lesser than the mid
Step 5- If mid element == item return with the position where found
Step 6- Else keep doing the above steps until you violate the bounds of the array
We are going to be discussing two methods here –
// Binary Search implimentation in C (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include<stdio.h>
int binarySearch(int arr[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (arr[mid] == item)
return mid;
// goes to recursive calls in left half
if (arr[mid] > item)
return binarySearch(arr, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(arr, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
int main(){
// array needs to be sorted to impliment binary search
int arr[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 70;
int position = binarySearch(arr, 0, n-1, item);
if(position == -1)
printf("%d Not Found",item);
else
printf("%d Found at index : %d",item, position);
}
// Binary Search implimentation in C++ (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include<bits/stdc++.h>
using namespace std;
int binarySearch(int array[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (array[mid] == item)
return mid+1;
// goes to recursive calls in left half
if (array[mid] > item)
return binarySearch(array, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(array, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
int main(){
int array[10] = {3, 5, 7, 9, 12, 70, 16, 18, 19, 22};
int item = 70;
int position = binarySearch(array, 0, 10, item);
if(position == -1)
cout<<"Not Found";
else
cout << item << " Found at position : " << position;
}
// Binary Search implimentation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{
public static int binarySearch(int array[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (array[mid] == item)
return mid;
// goes to recursive calls in left half
if (array[mid] > item)
return binarySearch(array, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(array, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
public static void main(String args[]){
int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;
int position = binarySearch(array, 0, size-1, item);
if(position == -1)
System.out.println("Element not found");
else
System.out.println(item + " found at position: " + position);
}
}
// Time complexity O(Log N)
70 Found at index : 6
// Binary Search implimentation in C (Iterative)
// Time Complexity : O(N)
// Space Complexity : O(1)
#include<stdio.h>
// Returns index of item in given array, if it is present
// otherwise returns -1
int binarySearch(int arr[], int l, int r, int item)
{
while (l <= r) {
int mid = l + (r - l) / 2;
// if item is at mid
if (arr[mid] == item)
return mid;
// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
l = mid + 1;
// If item is smaller, ignore right half, consider only left half
else
r = mid - 1;
}
// if we are able to reach here
// means item wasn't present
return -1;
}
int main(void)
{
// array needs to be sorted to impliment binary search
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 30;
int position = binarySearch(arr, 0, n - 1, item);
if(position == -1)
printf("%d Not Found",item);
else
printf("%d Found at index : %d",item, position);
return 0;
}
// Binary Search implimentation in C++ (Iterative)
// Time Complexity : O(N)
// Space Complexity : O(1)
#include<bits/stdc++.h>
using namespace std;
// Returns index of item in given array, if it is present
// otherwise returns -1
int binarySearch(int arr[], int l, int r, int item)
{
while (l <= r) {
int mid = l + (r - l) / 2;
// if item is at mid
if (arr[mid] == item)
return mid;
// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
l = mid + 1;
// If item is smaller, ignore right half, consider only left half
else
r = mid - 1;
}
// if we are able to reach here
// means item wasn't present
return -1;
}
int main()
{
// array needs to be sorted to impliment binary search
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 30;
int position = binarySearch(arr, 0, n - 1, item);
if(position == -1)
cout << item << " Not Found";
else
cout << item << " Found at index : " << position;
return 0;
}
// Binary Search implementation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{
public static int binarySearch(int array[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (array[mid] == item)
return mid;
// goes to recursive calls in left half
if (array[mid] > item)
return binarySearch(array, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(array, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
public static void main(String args[]){
int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 30;
int size = array.length;
int position = binarySearch(array, 0, size-1, item);
if(position == -1)
System.out.println("Element not found");
else
System.out.println(item + " found at index : " + position);
}
}
30 Found at index : 2
| Best | Average | Worst | Space Complexity | Average Comparision |
| O(1) | O(log n) | O(log n) | O(1) | Log(N+1) |