Learn Computer Science programming - C# and C++ Algorithms

 

Binary Search Recursive

This is a Divide-and-Conquer search algorithm that works on a sorted array. It works by continuously dividing the array into two halves and keeps searching for an item until it finds it. This is the implementation of a recursive algorithm. It requires much more memory.
Code
binarysearchrecursive.zip
File Size: 4221 kb
File Type: zip
Download File

#include <iostream>
#include <string.h>
#include <windows.h>
using namespace std;

#define E_Target_Not_In_Array -1
#define E_Array_UnOrdered -2
#define E_Limits_Reversed -3

int BinarySearchRecursive(int * array, int lower, int upper, int target)
{
// This recursive function has more overhead and less efficiency than its non recursive counterpart
// It only serves to changes the limits.
int center, range;

range = upper-lower;
if (range <0)
return E_Limits_Reversed;
else if (range == 0 && array[lower] != target)
return E_Target_Not_In_Array;

if (array[lower] > array[upper])
return E_Array_UnOrdered;
center = ((range)/2) + lower;
if (target == array[center])
return center;
else if (target < array[center])
return BinarySearchRecursive (array, lower, center - 1,target);
else
return BinarySearchRecursive (array, center + 1, upper, target);
}

void main()
{
int x;
wcout <<  endl << "*** Binary Search Recursive ***" << endl;
wcout << "*************************************************" << endl;
int numbers[] = {11,12,23,44,45,47,48,88,91,92,97};
int number = BinarySearchRecursive (numbers,0,10,12);
cout << "I found the number 12. It is array element # " << number <<endl;
number = BinarySearchRecursive (numbers,0,10,91);
cout << "I found the number 91. It is array element # " << number <<endl;
cin >> x;
 }