算法题,搜索插入位置,二分查找慢的思考

今天做算法题遇到一个问题,两种方法一个用到了php的array_search函数 一个用到了二分查找,想知道为什么二分查找要比数组循环的要慢,希望知道的留言。

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

示例 3:

输入: [1,3,5,6], 7

输出: 4

普通php解法

class Solution {

/**

* @param Integer[] $nums

* @param Integer $target

* @return Integer

*/

function searchInsert($nums, $target) {

$index = array_search($target,$nums);

if($index !== false){

return $index;

}

foreach($nums as $k => $v){

if($v > $target){

return $k;

}

}

return $k + 1;

}

}

二分法,不知道为什么执行速度比上面循环还慢~

class Solution {

/**

* @param Integer[] $nums

* @param Integer $target

* @return Integer

*/

function searchInsert($nums, $target) {

$index = array_search($target,$nums);

if($index !== false){

return $index;

}

$l = 0;$r = count($nums) - 1;

while($l <= $r){

$mid = floor(($l + $r)/2);

if($nums[$mid]<$target){

$l = $mid + 1;

}else{

$r = $mid - 1;

}

}

return $l;

}

}

有知道原因的请在评论区留言

发表评论
留言与评论(共有 0 条评论)
   
验证码:

相关文章

推荐文章

'); })();