Recursive Binary Search in Cpp Programming

Write a program to find a number in a array using Recursive Binary Search.

Meaning of Recursive

Recursive function is a function which calls itself during its execution. Similar Like Loop.

Working

Recursive Binary Search is Working with the Sorted Array. if the array is not sorted then using Sorting Algorithm make an Array to Sort. In Recursive Binary Search Compare start from the middle of array if Searching Element is lower is middle goes to left side one by one, if the Searching Element is Greater then the middle Element its goes right side one by one in recursive order. If found it Return its Index which is 0 or above 0 and When number is not it Return -1 as response.

Function

• function binary_search(array[],length,search_number,lower,upper)
  • if(lower <= upper)
    • center = (lower+upper)/2;
    • if(search_number == array[center])
      • return center // It Exit When Number is Found
    • else if(search_number < array[center])
      • return binary_search(array,length,search_number,lower,center-1) // Recall Itself going Left Side of Sub Array
    • else
      • return binary_search(array,length,search_number,center+1,upper) // Recall Itself going Right Side of Sub Array
  • else // When All Element is And Not Match is Found
    •  return -1
• End Function

Main Program

• Make An Array
• If Un-Sorted Array
  • Make the Sorted Array
• lower = 0
• upper = length-1 (Ex. 8-1=4)
• search_number = 45
• found = binary_search(array[],length,search_number,lower,upper)
• if(found>-1)
  • Found having Index
• else
  • Not Found

Program

//Recursive Binary Search
#include<iostream.h>
#include<conio.h>
void display_array(int array[],int length){
for(int i=0;i<length;i++){
cout<<array[i];
(i==length-1)? cout<<".":cout<<",";
}
}
//binary_search(array,length,search_number,lower,upper)
int binary_search(int array[],int length,int search_number,int lower,int upper){
if(lower <= upper){
int center = (lower+upper)/2;
if(search_number == array[center]){
return center;
}else if(search_number < array[center]){
return binary_search(array,length,search_number,lower,center-1);
}else{
return binary_search(array,length,search_number,center+1,upper);
}
}else{
return -1;
}
}
void sorting(int array[],int length){
for(int i = length - 1; i >= 0; i--){
for(int j = 1; j <= i; j++){
if(array[j-1] > array[j]){
//Swap
int temp_A = array[j-1];
array[j-1] = array[j];
array[j] = temp_A;
}
}
}
}
void main(){
clrscr();
int array[10]={12,34,21,39,65,48,36,11,58,23};
int number,index;
int length=10;
cout<<"\n Recursive Binary Search";
cout<<"\n -----------------------";
cout<<"\n Un-Sorted Elements in a Array ";
display_array(array,length);
//Sorting
cout<<"\n\n Recursive Binary Search is Works With Sorted Array.. ";
sorting(array,length);
cout<<"\n\n After Sorting Sorted Elements in a Array ";
display_array(array,length);
cout<<"\n Enter Number to be Search : ";
cin>>number;
int lower=0; // Left of Array Segment
int upper=length-1; // Right of Array Segment
index = binary_search(array,length,number,lower,upper);
if(index>-1){
cout<<"\n Number Found at index of "<<index;
}else{
cout<<"\n "<<number<<" is not Found in Array ";
}
getch();
}

Output

Number is Found

Number is Not Found