c++ - Significance of Equal To in Binary Search -
i implementing binary search in c++. here code:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int bs(vector<int> a, int val) { int l =0, r = a.size()-1; while(l<=r) // significance of == { int mid = l + (r-l)/2; if(a[mid]==val) return mid; if(a[mid]>val) { r = mid-1; continue; } else { l = mid + 1 ; } } return l; // deliberately returning } int main() { vector<int> = {1,3}; cout << bs(a,1) <<endl; return 0; }
question 1
in implementations, see people use
while(l<r)
while in use
while(l<=r)
is there conceptual difference between preferring 1 way ? possible sources of error if don't use == ?
question 2
in case element not found, l guaranteed position in element inserted list still remains sorted ? valid while using equal or not using equal ?
it depends on how calculating variable r
. in case
r = a.size()-1;
so correct usage while(l<=r)
if calculate r r = a.size();
correct usage while(l<r)
in case element not found, l guaranteed position in element inserted list still remains sorted ?
you didn't sort vector, proper binary search, vector should sorted before calling binary search.
std::sort(std::begin(a),std::end(a));
and header provide std::binary_search
, instead reinventing wheel can use follows:
std::binary_search(std::begin(a),std::end(a),val);
binary search supposed return value of index in vector, if find. there no guarantee should provide next location insertion.
is valid while using equal or not using equal ?
i explained in first part of answer.
Comments
Post a Comment