Recursive Binary Array Search

[Chevytuff19]

Hello,

I am having an issue with my code...here is what it is supposed to do:

The function performs a binary search of the range [first, last] for itemToFind. The function returns an address i in the range [first, last] such that *i == itemToFind. The function returns NULL if no such address exists. ***It has to be recursive, however.

I get the basic concept of searching, but this function accepts two pointers to arrays instead of an array and an integer like I am used to.

Here is the whole program; the commented stuff is the main part, I just have to write the BinarySearch function...any help would be greatly appreciated. :)

#include <iostream>
#include <string>

using namespace std;

// template function prototype
template<typename T>
const T *BinarySearch(const T *first, const T *last, T itemToFind)
{
	int middle;
	bool found = false;

	while (first <= last && !found)
	{
		middle = (first + last) >> 1;	
	
		if (itemToFind == first[middle])
			return &first[middle];
		else
			BinarySearch(middle, last, itemToFind);
	}

	return NULL;
}

/*#include "lab22.C"

template<typename T>
void PrintArray(const T *array, int count)
{
  const T *ptr;
  const T *const endPtr = array + count;

  for (ptr = array; ptr < endPtr; ptr++)
    cout << *ptr << " ";

  cout << endl;
}

template<typename T>
void PrintAndSearch(const T *array, int n, T itemToFind, string nameOfArray)
{
  const T *ptr;

  cout << "Array " << nameOfArray << " contains:" << endl;
  PrintArray(array, n);
  ptr = BinarySearch(array, array + (n - 1), itemToFind);
  cout << itemToFind;
  if (ptr)
    cout << " is in array " << nameOfArray << " and is located at index "
         << ptr - array << endl << endl;
  else
    cout << " is not in array " << nameOfArray << endl << endl;
}

int main()
{
  const int aCount = 5, bCount = 7, cCount = 26, dCount = 10;
  int a[aCount] = {5, 15, 25, 35, 45};
  double b[bCount] = {1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7};
  char c[cCount] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                    'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                    'u', 'v', 'w', 'x', 'y', 'z'};
  string d[dCount] = {"Audi", "BMW", "Bentley", "Buick", "Cadillac",
                      "Chevrolet", "Dodge", "GMC", "Jaguar", "Lexus"};

  PrintAndSearch(a, aCount, 25, "a");
  PrintAndSearch(a, aCount, 55, "a");
  PrintAndSearch(b, bCount, 1.1, "b");
  PrintAndSearch(b, bCount, 11.11, "b");
  PrintAndSearch(c, cCount, 'z', "c");
  PrintAndSearch(c, cCount, 'Z', "c");
  PrintAndSearch(d, dCount, static_cast<string>("Cadillac"), "d");
  PrintAndSearch(d, dCount, static_cast<string>("Mercedes"), "d");

  return 0;
}*/

[therockon7throw]

Hi

See

http://www.cplusplus.com/reference/algorithm/binary_search/
and
http://www.cplusplus.com/reference/algorithm/lower_bound/

[Chevytuff19]

I looked at those links and, while very useful, I still have some issues. I think my problem is that the function takes in two arrays for first and last. I am not sure how to work with those to get the midpoint, for example...

[therockon7throw]

Hi
The function takes two iterators(pointers) and not two arrays, two iterators which point to the first and last element so if you hava a good look at the second link provided above will see that you could compute the middle point.

count = distance(first,last);
step=count/2;

where count and step are type of ptrdiff_t.

and distance is nothing else than

a ptrdiff_t

it = first;
ptrdiff_t n = 0 
while(it != last){
    n++;
  it++;

}

hope it helps