俗话说,面试造飞机,工作拧螺丝。拧了3年螺丝,也该造造飞机了。
打算面试头条,据说算法要求很高,先从基本的热热身。
二分查找算法
二分查找也称折半查找,是一种效率较高的查找方法。但是要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
算法复杂度:log2(n)
。
查找逻辑:
- 假设线性表升序排列。
- 将表中间位置数据和查找的数据进行比较,如果相等,则查找成功,返回索引值。
- 否则,将当前线性表切分为前表和后表。
- 如果当前值小于目标值,则从后表继续查找。
- 如果大于目标值,则从前表继续查找。
- 重复以上过程,直到查找成功,或者子表不存在。
Javascript实现方式
/**
* 二分查找算法
* @params value 需要查找的目标值
* @params arr 需要查找目标值的数组,即单向线性表
* @params start 开始查找的下标
* @params end 结束查找的下标
* @return 查找到目标值,返回对应下标;否则,返回-1
*/
function divide2Find(value, arr, start, end) {
// 如果等于左右两侧,直接返回;否则当查找范围<2,则表明该值不存在
if (value === arr[start]) {
return start;
} else if (value === arr[end]) {
return end;
} else if (end - start < 2) {
return -1;
}
// 二分,取中间值比较;如果不匹配,根据大小指定方向,二分递归查找
let index = Math.floor((start + end) / 2);
let cur = arr[index];
if (cur === value) {
return index;
} else if (cur > value) {
return divide2Find(value, arr, start, index);
} else {
return divide2Find(value, arr, index, end)
}
}
// 算法函数调用
const arr = [3, 5, 6, 7, 9, 12, 15];
divide2Find(5, [3, 5, 6, 7, 9, 12, 15], 0, arr.length - 1); // 1
divide2Find(13, [3, 5, 6, 7, 9, 12, 15], 0, arr.length - 1); // -1
PHP实现方式
除了语法之外,和上面的JS思路完全一致,不再赘述注释。
function divide2Find($value, $arr, $start, $end) {
if ($value === $arr[$start]) {
return $start;
} else if ($value === $arr[$end]) {
return $end;
} else if ($end - $start < 2) {
return -1;
}
$index = floor(($end + $start) / 2);
$cur = $arr[$index];
if ($cur === $value) {
return $index;
} else if ($cur > $value) {
return $this->divide2Find($value, $arr, $start, $index);
} else {
return $this->divide2Find($value, $arr, $index, $end);
}
}
// 算法函数调用
$arr = [3, 5, 6, 7, 9, 12, 15];
echo $this->divide2Find(5, $arr, 0, count($arr) - 1); // 1
echo $this->divide2Find(13, $arr, 0, count($arr) - 1); // -1