We help IT Professionals succeed at work.
Get Started

Binary Search using Vector in C++

angel7170
angel7170 asked
on
255 Views
Last Modified: 2012-05-12
Hello,

I am trying to write a program that will generate and display a list of random numbers in an ascending order. Then the user enter a number to search. If the number entered matches one of the numbers in the list, the system will indicate the position of that number in the list. If the number entered does not match one of the numbers in the list, the system will display a message saying that the number cannot be found, but with its probable position.

The issue I have is, if the user enter a number that is beyond the range then I want to display the position to be the last position + 1. but now it throws an error "debug assertion failed" error.
Also, right now I am using two binary functions one if it is found and another for not found. Is there a way to combine into one function.

Please assist.

Thank you

// SearchNumber.cpp : Defines the entry point for the console application.
//

#include <stdafx.h>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <time.h>
#include <ctime>

using namespace std;

const int FAILURE = -1;


void swap(int& x, int& y)
{
	int temp = x;
	x= y;
	y = temp;
}

void print (vector<int> a)
{
	for (int i= 0; i< a.size(); i++)
		cout << a[i] << " ";
	cout << "\n";
}

void rand_seed()
{
	int seed = static_cast<int>(time(0));
	srand(seed);
}

int rand_int(int a, int b)
{
	return a + rand() % (b-a + 1);
}

int binarysearch(vector<int> v, int from, int to, int value) 
{ 
	if (from > to)
		return -1;
	int mid = (from + to)/2;
	if (v[mid] == value)
		return mid;
	else if (v[mid] < value)
		return binarysearch(v, mid+1, to, value);
	else
		return binarysearch(v, from, mid-1, value);
}

int binarysearch_notfound(vector<int> v, int from, int to, int value) 
{ 
	if (from > to)
		return from;
	int mid = (from + to)/2;
	if (v[mid] == value)
		return mid;
	else if (v[mid] < value)
		return binarysearch_notfound(v, mid+1, to, value);
	else
		return binarysearch_notfound(v, from, mid-1, value);
}



int main()
{
	
	rand_seed();
	vector<int> v(20);
	for (int i=0; i < v.size(); i++)
	v[i] = rand_int(1,100);
	//print(v);
	int a = 0;
	int b = v.size();
	
	cout << "The following are the generated random numbers:\n";
	sort(v.begin(), v.end());
	print(v);
	cout << endl;
	int search;
	cout << "Please enter a number to search for: \n" ;
	cin >> search;

	int result = binarysearch(v, a, b, search);
	int result_notfound = binarysearch_notfound(v, a, b, search);
	
	if (result != FAILURE)
		 cout << "Found in position [" << result << "]" << endl;
	else
		cout << "Not Found. Should go before position [" << result_notfound << "]" << endl;

	
	return 0;
}

Open in new window

Comment
Watch Question
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
Unlock 1 Answer and 2 Comments.
See Answer
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE