Using Divide and Conquer Strategies design a function for Binary Search using C++/ Java/ Python/ Scala.
#include<iostream>
#include<stdio.h>
#include <bits/stdc++.h>
using namespace std;
int binary_search(int array[],int low, int high, int key); //function declaration
int main()
{
int low,high,length,i,key;
cout<<"Enter the length Of array"<<endl;
cin>>length;
int array[length+1];
cout<<"Enter the elements of the array"<<endl;
for(i=0;i<length;i++)
{
cin>>array[i];
}
cout<<"Sorting the array as follows:"<<endl;
sort(array, array+length); //sorting array using sort function in STL
for(i=0;i<length;i++)
{
cout<<array[i]<<"\t";
}
cout<<"\nEnter the key to be searched"<<endl;
cin>>key;
high=length-1;
low=0;
int position=binary_search(array,low,high,key); //function call
if (position==-1)
{
cout<<"Number not found";
}
else
cout<<"Number found at location "<<position+1<<endl;
}
int binary_search(int array[],int low, int high, int key)
{
if(low>high)
return -1;
else
{
int mid=(low+high)/2; //calculate centre postion in array
if(array[mid]==key)
{
return mid;
}
else if(array[mid]<key)
{
low=mid+1;
return(binary_search(array,low,high,key)); //search in right half of array
}
else if(array[mid]>key)
{
high=mid-1;
return(binary_search(array,low,high,key)); //search in left half of array
}
}
}
OUTPUT:
#include<iostream>
#include<stdio.h>
#include <bits/stdc++.h>
using namespace std;
int binary_search(int array[],int low, int high, int key); //function declaration
int main()
{
int low,high,length,i,key;
cout<<"Enter the length Of array"<<endl;
cin>>length;
int array[length+1];
cout<<"Enter the elements of the array"<<endl;
for(i=0;i<length;i++)
{
cin>>array[i];
}
cout<<"Sorting the array as follows:"<<endl;
sort(array, array+length); //sorting array using sort function in STL
for(i=0;i<length;i++)
{
cout<<array[i]<<"\t";
}
cout<<"\nEnter the key to be searched"<<endl;
cin>>key;
high=length-1;
low=0;
int position=binary_search(array,low,high,key); //function call
if (position==-1)
{
cout<<"Number not found";
}
else
cout<<"Number found at location "<<position+1<<endl;
}
int binary_search(int array[],int low, int high, int key)
{
if(low>high)
return -1;
else
{
int mid=(low+high)/2; //calculate centre postion in array
if(array[mid]==key)
{
return mid;
}
else if(array[mid]<key)
{
low=mid+1;
return(binary_search(array,low,high,key)); //search in right half of array
}
else if(array[mid]>key)
{
high=mid-1;
return(binary_search(array,low,high,key)); //search in left half of array
}
}
}
OUTPUT:
No comments:
Post a Comment