Given an array of integers nums
which is sorted in ascending order, and an integer target
, write a function to search target
in nums
. If target
exists, then return its index. Otherwise, return -1
.
當找到想要的目標,就顯示我的答案,如果數列沒有我的目標就顯示 -1
使用二分法,因為已經排序過。可以讓時間複雜度在 O(log(n))
通過左右邊界找到中點,如果為要找的數返回,否則移動邊界,找不到,返回 -1。
var search = function (nums, target) {
let left = 0; // 初始左边界
let right = nums.length - 1; // 初始右边界
// 如果left > right 证明整个数组结束了仍没有找到目标值
while (left <= right) {
let mid = left + Math.floor((right - left) / 2); //防止溢出
if (target === nums[mid]) {
return mid;
} else if (target > nums[mid]) {
// 目标值大于中值,则中间左侧可以抛弃了
left = mid + 1;
} else {
// 目标值小于中值,则中间右侧可以抛弃了
right = mid - 1;
}
}
return -1;
};
- 排序後的數組
- 限定時間複雜度的搜尋法(題目限定 O(n)以下的解法)
- Others
- 用二元搜尋,每次都要先 Sorted Array。因此追加資料時,必須插入恰當的位置,需要付出維護陣列的代價。
- 線性搜尋,陣列的數據雜亂無章也無所謂。