Задача: Бинарный поиск в массиве и его разновидности
Исходник: Оптимизация основной версии: возращение первого вхождения, язык: C++ [code #190, hits: 13605]
автор: David [добавлен: 21.12.2006]
  1. template<class T> int BSearch(T* v, int n, T& t)
  2. {
  3. int l = -1, u = n, m;
  4.  
  5. while(l+1 != u)
  6. {
  7. m = (l + u) >> 1;
  8. if(v[m] < t) l = m;
  9. else u = m;
  10. }
  11.  
  12. return (u >= n || v[u] != t) ? -1 : u;
  13. }
Небольшая оптимизация реализации основной версии двоичного поиска с возвратом первого вхождения.
Эффективнее ~20-30% (за счет использования операции сдвига >> для получения середины диапазона)

+добавить реализацию