PHP算法之二分查找和顺序查找

一、二分查找 (数组里查找某个元素)

/**
 * 二分查找 (数组里查找某个元素)
 * $k为要查找的关键字（注：待查找的数组元素为奇数个）$low为查找范围的最小键值，$high为查找范围的最大键值  
 */
$low = min(array_keys($array));
$high = max(array_keys($array));
function dichotomy_search($array, $low, $high, $k) {
    if ($low <= $high) {
        $mid = intval ( ($low + $high) / 2 );
        if ($array [$mid] == $k) {
            return $mid;
        } elseif ($k < $array [$mid]) {
            return dichotomy_search ( $array, $low, $mid - 1, $k );
        } else {
            return dichotomy_search ( $array, $mid + 1, $high, $k );
        }
    }
    return -1;
}

二、顺序查找 (数组里查找某个元素)

/**
 * 顺序查找 (数组里查找某个元素)
 * $array为数组，$k为要查找的值  
 */
function sequential_search($array, $k) {
    $n = count($array);
    $array[$n] = $k;                //新建一个元素，并将k存放进去  
    for($i = 0; $i < $n; $i++) {
        if($array[$i] == $k) {
            break;
        }
    }
    if($i < $n) {                 //如果在新元素的前面找到了要找的值，则返回该值 
        return $i;
    } else {
        return -1;
    }
}