Binary search using a random array of integers--Sort problems

[helo12]

So I am trying to use a sort function before inputting an array of random integers into a binary search function first I tried using std::sort but that ran me into a bunch of errors in the #include<algorithm> file I have been pounding my head against this because I want to use it in a later assignment for black jack. Anyway here is the code. As you can see I have experimented with a lot

#include <iostream>
#include<stdlib.h>
#include<ctime>
#include<algorithm>
#include <vector>
using namespace std;


int LinearSearch();
int BinarySeach(const int ArrayofNums[], int SIZE, int value);
void BubbleSort(int ArrayOfNums[], int SIZE);
int main()
{
//variable declaration
const int SIZE=20;
int ArrayOfNums[SIZE]={0};
int x=1,y=0;
int value;
int results;
//establish randomization
srand(time(NULL));
//establish array size and values
ArrayOfNums[0]=rand()%100+1;

do{ ArrayOfNums[x]=rand()%100+1;
y=0;
while (y<x)
{
if (ArrayOfNums[y]==ArrayOfNums[x])
{x--;break;}
y++;}
x++;}
while (x<20);
//test to make sure that array is OK

for (x=0;x<20;x++){
cout<<ArrayOfNums[x]<<" ";
cout<<((ArrayOfNums[x]<10) ? " " : "");
cout<<(((x+1)%13==0) ? "\n" : "");}
cout<<"What would you like to search for?"<<endl;
cin>>value;

int BinarySeach(const int ArrayofNums[], int SIZE, int value);

results=BinarySeach(ArrayOfNums,SIZE,value);

if(results==-1){
cout<<"That number is not in this random set of numbers"<<endl;
}else{
cout<<"result found! "<<value<<" was found at "<<results<<"!"<<endl;}



return 0;}

void BubbleSort(int ArrayOfNums[], int SIZE)
{
int count = SIZE;
bool moved;
do
{
moved = false;
for (int i = 0; i < count-1; i++ )
{
if ( ArrayOfNums[i] > ArrayOfNums[i+1] )
{
int temp = ArrayOfNums[i];
ArrayOfNums[i] = ArrayOfNums[i+1];
ArrayOfNums[i+1] = temp;
moved = true;
}
}
count--;
}
while (moved);
}
int BinarySeach(const int ArrayofNums[], int SIZE, int value){
void BubbleSort(int ArrayOfNums[], int SIZE);
int first=0,
last=SIZE-1,
middle,
position=-1;
bool found=false;

while(found!=true && first<=last){
middle=first+last/2;

if(ArrayofNums[middle]==value){

found=true;
position=middle;
cout<<"middle"<<endl;

}else if(ArrayofNums[middle]>value){

last==middle-1;
cout<<"less"<<endl;}

else{first==`middle+1;
cout<<"more"<<endl;
}

return position;
}
}

[Chervil]

I don't know what problem you had with std::sort, it sounds like maybe the compiler is misconfigured in some way.

This should work:

    std::sort(ArrayOfNums, ArrayOfNums+SIZE);

or call your own sort function like this:

    BubbleSort(ArrayOfNums, SIZE); 

Do that inside main(). It looks like you were considering calling the function inside the search function, which would mean the array was sorted unnecessarily if you wanted to call the search function more than once.

A couple of other comments. You defined the constant SIZE but in two places still used the value 20 instead. Make sure the constant is used throughout, it makes the code easier to read and maintain.

Here the == operator should be =. There's also a spurious `character.

last==middle-1;
else{first==`middle+1;

[JLBorges]

> I tried using std::sort but that ran me into a bunch of errors in the #include<algorithm> file
> I want to use it in a later assignment for black jack.

If you are allowed to use std::sort, perhaps you would also be allowed to use binary search algorithms in <algorithm>

Something along these lines, perhaps:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <random>

// create a random sequence of n elements filled with values in [minv,maxv]
// return a vector see: https://cal-linux.com/tutorials/vectors.html
std::vector<int> make_random_seq( std::size_t n, int minv, int maxv )
{
    // default random number engine, seeded with the current time
    // http://www.cplusplus.com/reference/random/default_random_engine/
    static std::default_random_engine rng( std::time(nullptr) ) ;

    std::vector<int> seq ;

    // http://www.cplusplus.com/reference/random/uniform_int_distribution/
    std::uniform_int_distribution<int> distrib( minv, maxv ) ;
    while( seq.size() < n ) seq.push_back( distrib(rng) ) ;

    return seq ;
}

// check if an element with value 'value' is present in the sorted sequence
// return the index of the element in the sequence if it was found
// return an invalid position if it was not found
std::size_t bin_search( const std::vector<int>& sorted_seq, int value )
{
    // get an iterator to the first element in sorted_seq that is not less than v
    // auto: http://www.stroustrup.com/C++11FAQ.html#auto
    const auto iter = std::lower_bound( sorted_seq.begin(), sorted_seq.end(), value ) ;

    // if such an element was found and it is equal to v, return the position of that element
    if( iter != sorted_seq.end() && *iter == value ) return iter - sorted_seq.begin() ;

    else return sorted_seq.size() ; // otherwise return an invalid position
}


int main()
{
    const int SIZE = 40 ;

    // generate a sequence of random integers
    std::vector<int> seq = make_random_seq( SIZE, 1, 100 ) ;

    std::sort( seq.begin(), seq.end() ) ; // sort the sequence

    // print the sorted sequence using a range based loop
    // http://www.stroustrup.com/C++11FAQ.html#for
    for( int v : seq ) std::cout << v << ' ' ;
    std::cout << '\n' ;

    // binary search, and print out the result
    // initialiser list: http://www.stroustrup.com/C++11FAQ.html#init-list
    for( int v : { 13, 18, seq[SIZE/3], 40, seq[SIZE/2], 62, seq[ SIZE * 3/4 ], 80, 99 } )
    {
        const std::size_t pos = bin_search( seq, v ) ;

        // if the position is valid, print out the posion
        if( pos < seq.size() ) std::cout << v << " found at position " << pos << '\n' ;
        else std::cout << v << " was not found\n" ;
    }
}

http://coliru.stacked-crooked.com/a/2093ad711aedb125

[dhayden]

Please use code tags. Edit your post, highlight the code and click the <> button to the right of the edit window. That way we can refer to line numbers.

const int SIZE = 20;...
do ... while (x < 20);

The idea of using a const int here is that you can change the size of the array by changing the definition of SIZE. That only works if you use SIZE throughout the code so the while expression should be while (x < SIZE)

for (x = 0; x < 20; x++) { Same comment as above.

int BinarySeach(const int ArrayofNums[], int SIZE, int value){
void BubbleSort(int ArrayOfNums[], int SIZE);

Line 2 declares BubbleSort, it doesn't actually call it. You could change this, but I think it would be better to sort the data before calling BinarySearch at all. In other words, sort the data by calling BubbleSort in main(). Then call BinarySearch.

last == middle - 1; This has no effect because == is comparison. You want last = middle - 1;

return position; This is inside the while loop. It should be outside.

[helo12]

Thank you guys very much for the help