Существует известный алгоритм поиска элемента в отсортированном массиве, называемый бинарным (двоичным) поиском. Его суть заключается в делении массива на половины и сравнении искомого с элементом, который располагается в середине вновь получившегося отрезка. Многие реализации грешат мелкими недочетами и работают только в указанном диапазоне. Предлагаю Вам еще один вариант, в котором я постарался учесть все возможные ситуации, сохранив при этом красоту и структуру кода. Алгоритм реализован на PHP.

1. /**
2.  * Функция бинарного поиска по упорядоченному массиву
3.  * @param array $source_array Упорядоченный по возрастанию массив целых чисел
4.  * @param int $search_value Искомая величина
5.  * @return bool|int
6.  */
7. function binary_search(&$source_array, $search_value){
8. $count = count($source_array);
10. if($count < pow(2, 31) && is_int($search_value)){
11. $start = 0;
12. $end = $count — 1;
14. while(true){
15. $len = $end — $start ;
17. if($len > 2){
18. if($len % 2 != 0)$len++;
19. $mid = (int) ($len/2 + $start);
20. }elseif($len >= 0){
21. $mid = $start;
22. }else{
23. return false;
24. }
26. if($source_array[$mid] == $search_value){
27. while( ($mid != 0) && ($source_array[$mid — 1] == $search_value))
28. $mid—;
29. return $mid;
30. }elseif($source_array[$mid] > $search_value){
31. $end = $mid — 1;
32. }else{
33. $start = $mid + 1;
34. }
35. }
36. }else{
37. return false;
38. }
39. }

Алгоритм является классическим и в каких то особенных комментариях не нуждается.
Из полезного:

$count < pow(2, 31)

Здесь мы проверяем длину массива для защиты от переполнения буфера.


while( ($mid != 0) && ($source_array[$mid - 1] == $search_value))
$mid--;

Если в нашем исходном массиве нужное нам значение встречается несколько раз, то с помощью этого кода мы получим первое вхождение искомого значения в массив.

Использование:

$array = array(15,58,5954);
sort($array);
$search_value = 15;
if(false !== $result = binary_search(&$array, $search_value)){
var_dump("Result id:" . $result);
var_dump("Result value:" . $array[$result]);
}


Результатом работы функции является порядковый номер элемента в массиве (нумерация начинается с нуля). Если элемент не найден, то возвращается FALSE (необходимо строгое сравнение с false === или !==, т.к. функция может вернуть 0, если элемент в самом начале массива).