Блог пользователя mysskin

binary search
Автор mysskin, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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);
→ Ответить