Задача: Бинарный поиск в массиве и его разновидности
Исходник: Основная версия: возращение первого вхождения, язык: C++ [code #3, hits: 14889]
автор: this [добавлен: 18.04.2002]
  1. int BSearch(int x[], int n, int t) {
  2. int l = -1, u = n, p = 0, m = 0;
  3.  
  4. while (l + 1 != u) {
  5. m = (l + u) /2;
  6.  
  7. if (x[m] < t) {
  8. l = m;
  9. } else {
  10. u = m;
  11. }
  12. }
  13.  
  14. p = u;
  15. if (p >= n || x[p] != t) {
  16. p = -1;
  17. }
  18. return p;
  19. }
Реализация основной версии двоичного поиска.
В отсортированном массиве ищет элемент за не более чем log2n проходов, где n - длинна массива.
Если искомых элементов в массиве несколько - возвращается первый из них.
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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