Существует известный алгоритм поиска элемента в отсортированном массиве, называемый бинарным (двоичным) поиском. Его суть заключается в делении массива на половины и сравнении искомого с элементом, который располагается в середине вновь получившегося отрезка. Многие реализации грешат мелкими недочетами и работают только в указанном диапазоне. Предлагаю Вам еще один вариант, в котором я постарался учесть все возможные ситуации, сохранив при этом красоту и структуру кода. Алгоритм реализован на PHP.
-
/**
-
* Функция бинарного поиска по упорядоченному массиву
-
* @param array $source_array Упорядоченный по возрастанию массив целых чисел
-
* @param int $search_value Искомая величина
-
* @return bool|int
-
*/
-
function binary_search(&$source_array, $search_value){
-
$count = count($source_array);
-
if($count < pow(2, 31) && is_int($search_value)){
-
$start = 0;
-
$end = $count — 1;
-
while(true){
-
$len = $end — $start ;
-
if($len > 2){
-
if($len % 2 != 0)$len++;
-
$mid = (int) ($len/2 + $start);
-
}elseif($len >= 0){
-
$mid = $start;
-
}else{
-
return false;
-
}
-
if($source_array[$mid] == $search_value){
-
while( ($mid != 0) && ($source_array[$mid — 1] == $search_value))
-
$mid—;
-
return $mid;
-
}elseif($source_array[$mid] > $search_value){
-
$end = $mid — 1;
-
}else{
-
$start = $mid + 1;
-
}
-
}
-
}else{
-
return false;
-
}
-
}
Алгоритм является классическим и в каких то особенных комментариях не нуждается.
Из полезного:
$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, если элемент в самом начале массива).