Thursday, 6 July 2017

Using Divide and Conquer Strategies design a function for Binary Search using C++/ Java/ Python/ Scala.

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:

No comments:

Post a Comment