mysskin's blog

binary search
By mysskin, 9 years ago, In English

i want to binary search an array + i wanted to count the number of occurances in the array if element existed i wrote this method is there any problem with this ???

let e be the element to be searched and t be the vector

vectort;

int ans=0; sort(t.begin(),t.end()); if( binary_search(t.begin(),t.end(),e) ){

ib=lower_bound(t.begin(),t.end(),e);
ie=upper_bound(t.begin(),t.end(),e);
ans=distance(ib,ie);

}

ans contains the number of occurances of e

  • Vote: I like it
  • -17
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The binary_search is useless. If there is not element e, then lower_bound and upper_bound will return the same iterator and the distance will be 0. If you are worried about performance, then you can just check after the lower_bound if the element was found.

It's not very hard to try these things yourself. Just make some test cases yourself.

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

equal_range is exactly what you need:

sort(t.begin(), t.end());
auto bounds = equal_range(t.begin(), t.end(), e);
ans = distance(bounds.first, bounds.second);
→ Reply