Binary Search in Data Structure

Binary Search is a searching algorithm in data structure in which repeatedly the array is divided into half until the element to be searched is found.

For Example:

If we want to search 30 in the following Array:

Step-1: Firstly the array is of 5 elements then it is divided by 2 that is 5/2 means 3 element is compared firstly.

Step-2 : 30 is the third element then it is compared with the element to searched.

Step -3: It is matched then the element is found.

Advantages of Binary Search Over Linear Search

• Best for large amount of data.
• At each step the array is divided into half reduces space complexity
• Faster than Linear Search.

Disadvantage

• Can only be used for sorted array.
• Applicable on only single dimensional array .
• complicated than linear search.

Applications on Binary Search in real life

• Dictionary.
• Figure out resource requirement in larger system.
• Finding numerical solutions to the equations.

Binary Search Program in C++ Using Array

Group of element in any form of data structure is an array.

Program to search a number in c++ using array is as follows:

//To perform binary search//
#include<iostream>

using namespace std;

int main()
{
	int ar[10]={10,20,30,40,50,60,70,80,90,100};
	int lb,ub,mid,data,found;
	char z;
	cout<<"you want to enter array(y/n)\n";
	cin>>z;
	if(z=='y') {
		cout<<"enter 10 ementnts (assending order) for array\n";
		for(int i=0;i<10;i++)
			cin>>ar[i];
	}
	if(z=='n') {
		cout<<"your array\n";
		for(int i=0;i<10;i++)
			cout<<ar[i]<<"\t";
	}
	cout<<"\nenter data to search\n";
	cin>>data;
	lb=0;
	ub=9;
	mid=(lb+ub)/2;
	found=0;
	while((found==0) && (lb<=ub)) {
		cout<<"while loop begin:\t"<<"lb:"<<lb<<"\tub:"<<ub<<"\tmid:"<<mid<<"\n";
		if(ar[mid]==data){
			found=1;
			break;
		}
		if(ar[mid]>data)
			ub=mid-1;
		if(ar[mid]<data)
			lb=mid+1;
		mid=(lb+ub)/2;
		cout<<"while loop end:\t\t"<<"lb:"<<lb<<"\tub:"<<ub<<"\tmid:"<<mid<<"\n";
	}
	cout<<"search element "<<data<<" is";
	if(found==1)
		cout<<" found at position "<<mid+1;
	if(found==0)
		cout<<" not found\n";	
	return 0;
}

Output of the program in which number is to be searched using c++ in an array is as follows:

Binary Search Program in C++ Using Class

Binary Search Program in C++ Without Function

Program to search a number in c++ without function is as follows:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
	int list[100];
	int i,n,pos,x;
	int first,middle,last;
	char ch;
	do{
		cout<<"\n Enter the size of list: ";
		cin>>n;
		cout<<"\n Enter the Elements of the Array in Sorted order: \n";
		for(i=0;i<n;i++){
			cout<<" ";
			cin>>list[i];

		}
		first=0;pos=-1;last=n-1;
		cout<<"\n Enter the Value to be searched: ";
		cin>>x;
		//search the list.
		while((first<=last)&&(pos==-1)){
			middle=(first+last)/2;
			if(list[middle]==x)
			pos=middle;
			else
			if(list[middle]<x)
			  first=middle+1;
			else
			  last=middle-1;
		}
		if(pos>-1)
			cout<<"\n The Position of the element is:  "<<++pos;
		else
			cout<<"\n Search Unsuccessfull!!\n";

		cout<<"\nWant to continue(y/n):";
		cin>>ch;
	}while(ch=='y'||ch=='Y');
return 0;
}

Output of the program to be searched without function in c++ is as follows:

Binary Search in C

Program to search a element using c is as follows:

#include<stdio.h>

int main()
{
	int list[100];
	int i,n,pos,x;
	int first,middle,last;
	char ch;
	do{
		printf("\n Enter the size of list: ");
		scanf("%d",&n);
		printf("\n Enter the Elements of the Array in Sorted order: \n");
		for(i=0;i<n;i++){
			printf(" ");
			scanf("%d",&list[i]);

		}
		first=0;pos=-1;last=n-1;
		printf("\n Enter the Value to be searched: ");
		scanf("%d",&x);
		while((first<=last)&&(pos==-1)){
			middle=(first+last)/2;
			if(list[middle]==x)
			pos=middle;
			else
			if(list[middle]<x)
			  first=middle+1;
			else
			  last=middle-1;
		}
		if(pos>-1)
			printf("\n The Position of the element is: %d ",pos);
		else
			printf("\n Search Unsuccessfull!!\n");

		printf("\nWant to continue(y/n):");
		scanf("%c",&ch);
	}while(ch=='y'||ch=='Y');
return 0;
}

Output of the program to search a element in the c program is as follows:

Binary Search in Python

Program to search a element using python is as follows:

def binary_search(arr, a, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If found at mid, then return it
        if arr[mid] == a:
            return mid

        # Search the left half
        elif arr[mid] > a:
            return binary_search(arr, a, low, mid-1)

        # Search the right half
        else:
            return binary_search(arr, a, mid + 1, high)

    else:
        return -1
arr = input('Enter the list of numbers in ascending order ')
arr = arr.split();
arr = [int(x) for x in arr]
a = int(input('The number to search for: '))

index = binary_search(arr, a, 0, len(arr)-1)

if index != -1:
    print("Element is present at index " + str(index))
else:
    print("Not found")

Output of the program to search a element in the c program is as follows:

Related Link:

• Data Structure MCQ