今天做算法题遇到一个问题,两种方法一个用到了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 条评论) |