If you are looking for Binary search in c | c++ and java then you are at right article.
Binary search is a divide and conquer technique which searches an element in log ( n ).
One condition for binary search to work is that it should be sorted either in ascending or descending order based on implementation.
Working of Binary search algorithm
Inorder to perform binary search the array should be sorted.
If array is sorted in Ascending Order : Find the middle element by dividing the sum of first and middle by two. In the beginning first is assigned to start index and last is assigned to end index of the array that is size-1 of that array. After finding the middle index compare the element of the middle index is equal to the search key element. If not equal then check whether the middle element is smaller or greater than the search key element. If middle is smaller than search key search in the left subarray, else search in right subarray. That is if middle element is smaller than search key then assign the middle value to start otherwie assign the last index as middle-1
Perform this until first is lesser or equal to last index.
If array is sorted in Descending Order: Find the middle element by dividing the sum of first and middle by two. In the beginning first is assigned to start index and last is assigned to end index of the array that is size-1 of that array. After finding the middle index compare the element of the middle index is equal to the search key element. If not equal then check whether the middle element is smaller or greater than the search key element. If middle is greater than search key search in the left subarray, else search in right subarray.
That is if middle element is greater than search key then assign the last value to middle-1 otherwie assign the first index as middle+1
Perform this until first is lesser or equal to last index.
Programming pre requisites
- Datatypes in c, c++ and java.
- Comparisn operator in c, c++ and java.
- Input output operations in c, c++ and java.
- Loops in c, c++ and java.
- If else in c, c++ and java.
- Mathematical operators in c, c++ and java.
Efficiency of Binary Search algorithm
Now we consider two scenarios:
If array is sorted then we dont need to sort it hence the efficiency will be log ( n ).
If array is not sorted then we need to sort it hence the efficiency will be log ( n ) + nlog ( n ).
Binary search in c
#include<stdio.h>
int main(int argc, char const *argv[])
{
printf( "\nBinary Search in c\nThis method is iterative\n" );
int n,first,last,middle,search_element;
printf("Enter the total numbers in the array\n");
scanf("%d",&n);
int arr[n];
printf("Enter the array elements\n");
for( int i=0 ; i<n ; i++ )
{
scanf("%d",&arr[i]);
}
printf("Enter search element\n");
scanf("%d",&search_element);
first=0;
last=n-1;
middle=(first+last)/2;
while( first<=last )
{
if( arr[middle] == search_element )
{
printf( "Element %d found at %d",search_element,(middle+1) );
return 0;
}
else if( arr[middle]< search_element)
{
first=middle+1;
}
else
{
last=middle-1;
}
}
printf( "Element %d not found ",search_element );
return 0;
}
Binary search in c++
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
cout<<"\nBinary Search in c\nThis method is iterative\n";
int n,first,last,middle,search_element;
cout<<"Enter the total numbers in the array\n";
cin>>n;
int arr[n];
cout<<"Enter the array elements\n";
for( int i=0 ; i<n ; i++ )
{
cin>>arr[i];
}
cout<<"Enter search element\n";
cin>>search_element;
first=0;
last=n-1;
middle=(first+last)/2;
while( first<=last )
{
if( arr[middle] == search_element )
{
cout<<"Element"<<search_element<< "found at"<<(middle+1);
return 0;
}
else if( arr[middle]< search_element)
{
first=middle+1;
}
else
{
last=middle-1;
}
middle=(first+last)/2;
}
cout<<"Element"<<search_element<< "not found";
return 0;
}
Binary search in Java
import java.util.Scanner;
public class binary_search_in_java {
public static void main(String[] args) {
System.out.println("Binary search in Java");
int n;
System.out.println("This is iterative method");
System.out.println("Enter the number of elements");
Scanner stdin=new Scanner(System.in);
n=stdin.nextInt();
int[] array=new int[n];
System.out.println("Enter the elements");
for( int i=0 ; i<n ; i++ )
{
array[i]=stdin.nextInt();
}
int search_element=0;
System.out.println("Enter search element");
search_element=stdin.nextInt();
int first=0;
int last=n-1;
int middle=(first+last)/2;
while( first<=last )
{
if( array[middle]==search_element )
{
System.out.println("Element "+search_element+" found at "+(middle+1));
System.exit(0);
}
else if( array[middle]<search_element )
{
first=middle+1;
}
else
{
last=middle-1;
}
middle=(first+last)/2;
}
System.out.println("Element "+search_element+" not found ");
}
}
Further practice reading
- Armstrong number in C | C++ and Java
- Palindrome in C | C++ and Java
- Linear Search in C | C++ and Java
- Factorial program in C | C++ and Java
- Odd even program in c | c++ and java
- Bubble sort in c | c++ and java
- Binary search algorithm