Binary Searching of random number arrays

[MegsD]

we were tasked to find a specific number in the array, doesn't matter if its linear or binary, so I tried it in binary.

wow.cpp (library header (.cpp))

#include <iostream>
#include <cmath>

using namespace std;

void sort(double x[], int n)
{
	double currmin; //Keeps track of current minimum
	int currindex; //Keeps track of index of current minimum
	for (int i = 0; i < n - 1; i++)
	{
		currmin = x[i];
		currindex = i;
		for (int j = i + 1; j < n; j++)
		{
			if (x[j] <= currmin)
			{
				currmin = x[j];
				currindex = j;
			}
		}
		x[currindex] = x[i];
		x[i] = currmin;
	}
	return;
}

int binarySearch(double x[], int n, double value)
{
	int low = 0;
	int high = n - 1;

	int mid;

	while (low <= high)
	{
		mid = (low + high) / 2;

		if (value == x[mid])
		{
			return mid;
		}
		else if (value > x[mid])
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}

	return -1;

}

wow.h (library header (.h))

int binarySearch(double x[], int n, double value);
void sort(double x[], int n);

source.cpp (program code)

#include <iostream>
#include "wow.h"
using namespace std;

int main()
{
	double x[5];
	int n = 5;
	for (int i = 0; i < 5; i++)
	{
		x[i] = (double)rand() / RAND_MAX*(501.5 - 498.5) + 498.5;
		cout << x[i] << endl; //(add a // in the begining of this line to not show random numbers)
	}
	int UValue;
	cout << "Enter an integer: " << endl;
	cin >> UValue;

	sort(x, n);

	int result = binarySearch(x, n, UValue);

	if (result >= 0)
	{
		cout << "The number " << x[result] << " was found at the "
			"element with index " << result << endl;
	}
	else
	{
		cout << "The number " << UValue << " was not found. " << endl;
	}
	system("pause");
}

The problem is even if I inputted a number that I directly got from the output of random numbers it outputs [number] not found

[jlb]

Do you know that you really shouldn't compare floating point numbers for equality? Floating point numbers are approximations and can have various round off type of problems.

Jim

[MegsD]

Oh really? and No I did not, it was never discussed in class. Does that mean that I have to add a way to find the number within a specific percent error or something?

[jlb]

You may want to see this link: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
it explains floating point quite well.

[JLBorges]

> Does that mean that I have to add a way to find the number within a specific percent error or something?

That is one way of doing it: compare for equality with a tolerence.

The other possibility is to write the binary search using less than < and greater than > operators. This would imply that the comparison for equality is exact (between representable values):
for example searching for 0.0100000000001 won't find 0.01

std::size_t bsearch( const double a[], std::size_t low, std::size_t high, double value )
{
    if( low > high ) return std::size_t(-1) ; // return -1 cast to std::size_t if not found

    const std::size_t mid = low + (high - low) / 2 ;

    if( value < a[mid] ) return bsearch( a, low, mid-1, value ) ;
    else if( value > a[mid] ) return bsearch( a, mid+1, high, value ) ;
    else return mid ; // return the position within the array if found
}