### Binary Searching of random number arrays

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.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455`` ``````#include #include 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; }``````

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

source.cpp (program code)
 ``123456789101112131415161718192021222324252627282930313233`` ``````#include #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
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
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?
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.

> 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

 ``12345678910`` ``````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 }``````
Topic archived. No new replies allowed.