Answer to Question #326909 in C++ for Harry

Question

// Lab: Binary Search (find errors)

// Written by:

#include <iostream>

#include <cstdlib>

using namespace std;

int binarySearch(const int array[], int numElems, int value);

int main() {

  int list[100] = {5, 5, 8, 8, 8, 8, 9, 8, 9, 9, 10};

  int length = 11;

   

  for (int i = 0; i < length; i++) {

    cout << list[i] << " ";

  }

  cout << endl;

   

  for (int i = 0; i < 2 * length; i++) { // SEARCH 2 * length times

   

    int target = rand() % 5 + 5; // generate a random target within the range 5 to 10

    int location = binarySearch(list, length, target);

    if (location = - 1)

      cout << target << " NOT found!" << endl;

    else

    {

      // print a range: from index A to Z, inclusive!

      int z = location + 1;

      while( z < length && list[z] == list[location] )

        z++;

      z--;

       

      

   

Answer 1

#include <iostream>
#include <cstdlib>


using namespace std;


int binarySearch(const int arr[], int numElems, int value)
{
	int l = 0;
	int r = numElems-1;
	while (l <= r)
	{
		int m = l + (r - 1) / 2;
		if (arr[m] == value)
			return m;
		if (arr[m] < value)
			l = m + 1;
		else
			r = m - 1;
	}
	return -1;
}


int main()
{
	int list[11] = { 5, 5, 8, 8, 8, 8, 8, 9, 9, 9, 10 };
	int length = 11;
	for (int i = 0; i < length; i++)
	{
		cout << list[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < 2 * length; i++)
	{ // SEARCH 2 * length times
		int target = rand() % 5 + 5; // generate a random target within the range 5 to 10
		int location = binarySearch(list, length, target);
		if (location == -1)
			cout <<endl<< target << " NOT found!" << endl;
		else
		{
			// print a range: from index A to Z, inclusive!
			int z = location + 1;
			cout << endl <<target << " found at index: "<<z<<" ";
			z++;
			while (z < length && list[z] == list[location])
			{
				cout << z << " ";
				z++;
			}
		}
	}
}