patterncppMinor
Binary search feedback and improvements
Viewed 0 times
searchbinaryandfeedbackimprovements
Problem
I implemented the binary search algorithm. Input vector is sorted by
I would like to know if there are any stupid mistakes, bad practices that I used and how I can improve the code.
< than operator implemented by type T. The less than operator is expensive so we want to use it as few times as possible.I would like to know if there are any stupid mistakes, bad practices that I used and how I can improve the code.
template
long binary_search(const std::vector& v, const T& key){
if(v.empty()) { return -1; }
long lo = 0;
long hi = v.size() - 1;
long mid = (long) floor((lo + hi ) / 2);
long pmid = -1; // prev mid
while(lo = 0){
if( !(v[mid - 1] < key) && !(key < v[mid - 1])){
return mid - 1;
}
}
if(mid + 1 <= v.size()){
if(!( v[mid + 1] < key) && !(key < v[mid + 1] )){
return mid + 1;
}
}
return -1;
}Solution
You don't need to
When getting the mid value, this is safer:
This way you'll be safe from integer overflows, which can happen when adding two very large integers. (Or long, you get the point)
As you notice, there is some redundancy in the logic of seeing the mid before the main while loop and then again inside the loop, and also in the conditions within the loop and after it. Probably you can refactor this without redundancies, with most logic inside the loop, and almost nothing outside. There should be a return statement inside the loop when the element is found. The empty check will become unnecessary, as the loop condition will never be true for empty input.
floor the result of an integer division: the result is exactly the same without it.When getting the mid value, this is safer:
mid = lo + (hi - lo) / 2;This way you'll be safe from integer overflows, which can happen when adding two very large integers. (Or long, you get the point)
As you notice, there is some redundancy in the logic of seeing the mid before the main while loop and then again inside the loop, and also in the conditions within the loop and after it. Probably you can refactor this without redundancies, with most logic inside the loop, and almost nothing outside. There should be a return statement inside the loop when the element is found. The empty check will become unnecessary, as the loop condition will never be true for empty input.
template
long binary_search(const std::vector& v, const T& key){
long lo = 0;
long hi = v.size();
while (lo < hi) {
long mid = lo + (hi - lo ) / 2;
if (v[mid] == key) {
return mid;
}
if (v[mid] < key) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}Code Snippets
mid = lo + (hi - lo) / 2;template<class T>
long binary_search(const std::vector<T>& v, const T& key){
long lo = 0;
long hi = v.size();
while (lo < hi) {
long mid = lo + (hi - lo ) / 2;
if (v[mid] == key) {
return mid;
}
if (v[mid] < key) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}Context
StackExchange Code Review Q#93284, answer score: 2
Revisions (0)
No revisions yet.