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

Popular posts from this blog

android - Gradle sync Error:Configuration with name 'default' not found -

java - Andrioid studio start fail: Fatal error initializing 'null' -

html - jQuery UI Sortable - Remove placeholder after item is dropped -