# 前言
藉由 LeetCode 磨練演算法
# 題目連結
# 解題思路
# 暴力解
loop $nums
若有找到 $target
- 則第一次出現位置為 $left
- 最後一次出現位置為 $right
若都無找到 $target,return [-1, -1]
複雜度:
- 時間複雜度為 O(N)
- 空間複雜度為 O(1)
# binary search
透過兩次 binary search 分別找到 $left & $right
請配合參考下面的 solution code 幫助理解
要找出 $left,所以透過不斷的移動 $right 來縮小範圍
假如 $left 的初始位置就等同 $target,那最後 $left 與 $right 重疊,解除 $left < $right 的條件,得到 $left 為 $target 的最左側
假如 $target 不在 $nums 之內,那最終就是兩個結果。假設 $nums 最大值為 m,最小值為 n
- 當 $target 初始值就 < $nums 的最小值時,最終 $left 會跳出 $nums 的範圍
- 當 $target 初始值就 > $nums 的最大值時,最終 $right 會跳出 $nums 的範圍,而 $nums[$left] 會 !== $target
- 當 n < $target < m,但 $target 不存在於 $nums 時,這時最終取得的 $nums[$left] 會 !== $target
使用 while ($left < $right)
是因為當 $left 初始值就 === $target 時,最終勢必與 $right 重疊,若使用 while ($left <= $right)
會造成無限迴圈
尋找 $left 的 pivot 使用 intval($left + ($right - $left) / 2)
是因為當 $left 與 $right 相鄰時,必須要讓 $pivot 是偏左的,否則 if ($pValue >= $target)
的條件會造成無限迴圈
尋找 $right 的 pivot 使用 intval($left + ($right - $left) / 2 + 1)
是因為當 $left 與 $right 相鄰時,必須要讓 $pivot 是偏右的,否則 if ($pValue <= $target)
的條件會造成無限迴圈
當尋找 $left 且情境如下時,$pivot 必須使用 intval($left + ($right - $left) / 2)
當尋找 $right 且情境如下時,$pivot 必須使用 intval($left + ($right - $left) / 2 + 1)
透過兩次 binary search 便可以求得解答
複雜度:
- 時間複雜度為 O(logN)
- 空間複雜度為 O(1)
# solution code
<?php
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function searchRange($nums, $target) {
$left = 0;
$right = count($nums) - 1;
while ($left < $right) {
$pivot = intval($left + ($right - $left) / 2);
$pValue = $nums[$pivot];
if ($pValue >= $target) {
$right = $pivot;
} else {
$left = $pivot + 1;
}
}
if ($nums[$left] !== $target || !isset($nums[$left])) {
return [-1, -1];
}
$result[] = $left;
$right = count($nums) - 1;
while ($left < $right) {
$pivot = intval($left + ($right - $left) / 2 + 1);
$pValue = $nums[$pivot];
if ($pValue <= $target) {
$left = $pivot;
} else {
$right = $pivot - 1;
}
}
$result[] = $right;
return $result;
}
}