Задача: Последовательный поиск и его оптимизации
Исходник: Последовательный поиск, версия #3, язык: C# [code #60, hits: 10251]
автор: this [добавлен: 21.02.2006]
  1. public int SSearch3(int[] x, int t)
  2. {
  3. int size = x.Length;
  4.  
  5. // Временно сохраняем последний
  6. int hold = x[size - 1];
  7.  
  8. /* Если последний элемент искомый
  9. * то это нужно проверять сразу
  10. */
  11. if (hold == t) return size - 1;
  12.  
  13. x[size - 1] = t;
  14.  
  15. int i = 0;
  16. while (true)
  17. {
  18. if (x[i] == t) break;
  19. if (x[i + 1] == t) { i += 1; break; }
  20. if (x[i + 2] == t) { i += 2; break; }
  21. if (x[i + 3] == t) { i += 3; break; }
  22. if (x[i + 4] == t) { i += 4; break; }
  23. if (x[i + 5] == t) { i += 5; break; }
  24. if (x[i + 6] == t) { i += 6; break; }
  25. if (x[i + 7] == t) { i += 7; break; }
  26. i += 8;
  27. }
  28.  
  29. // Восстанавливаем значение последнего
  30. x[size - 1] = hold;
  31.  
  32. if (i == size-1)
  33. {
  34. return -1;
  35. }
  36. return i;
  37. }
Последовательный поиск, оптимизация вторая: добавление метки + сокращение циклов.

При поверхностном взгляде может сходу возникнуть вопрос: если длинна массива нечетна 8, то на последнем проходе мы выйдем за границу цикла если такого числа нет в массиве??? Этого не произойдет. Потому что благодаря введению метки - в массиве который просматривается в цикле - всегда будет содержаться искомый элемент. Просто если его нет в исходном массиве, то индекс его будет равен == (размер массива - 1), а это равносильно тому, что его нет!

При этом ситуацию, когда искомый элемент находится в конце исходного массива - нужно отфильтровывать в самом начале, т.к. потом присутствие искомого элемента в конце - приравнивается к отрицательному результату поиска.
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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