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.
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.
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