Binary Search

[honda933]

Hi All,

I need help writing a binary search program for my assignment. I don't have much started, and I need to get this complete.

bool binarySearch(const vector<int>& v, int k);

Write a function called binarySearch that finds an occurrence of an integer k in a vector v using binary search. The function declaration is given above. Write your own implementation of binary search; do not use the search function available in the C++ standard library.





#include <iostream>
#include <vector>

using namespace std;

bool binarySearch(const vector<int>& v, int k);
{


}

int main()
{



return 0;
}

[Calcushtag]

If you want to copy-paste then there are tons of code on internet, just google it. But just try to code the algorithm in your text book then ask for help if you can't debug it by your self.

[honda933]

Hi Calcushtag,

Thank you for the encouragement. I've given the program my first start. Though I'm getting errors (which isn't surprising).

I'm struggling to understand the question asked by my professor. Perhaps you can help me understand the question and concept behind the program.



#include <iostream>
#include <vector>

using namespace std;

bool binarySearch(const vector<int>& v, int k)
{
if(binarySearch = k)
{
return true;
}
else
{
return false;
}
}

int main()
{

vector<int> vect1;

vect1.push_back(1);
vect1.push_back(2);
vect1.push_back(3);
vect1.push_back(2);

binarySearch(vect1, 2);

if(binarySearch == true)
{
cout << "The occurence was found to be 2" << endl;
}
else
{
cout << "No occurence was found." << endl;
}
return 0;
}

[Calcushtag]

Replace Bold-Texts with actuall c++ code

bool binarySearch(const vector<int>& v, int k)
{
//find beginning and ending of vector
low = first Index of vector 'v'
high = last index of vector 'v'
mid = (low + high) /2;

//if k is not in v then low grows up and high shrinks down till low is equal or higher than high
if(low == high && k != v[mid)
return false;
//check if v's element at mid is equal to
if(k== v[mid])
return true; //OK. YOU Find to the k in v
else if(k< v[mid])
{
make new vector named v2 which contains elements of 'v' from index 'low' to index 'mid-1'
return binarySearch(v2, k);
}
else if(k > v[mid])
{
make new vector named v2 which contains elements of 'v' from index 'mid+1' to index 'high'
//now you can search upper part of v by:
return binarySearch(v2, k);
}
}

the above code is not master work (made it easy for understanding) but will work. if you succeed then may be you can improve it.

NOTE: binary search works on sorted arrays or vectors