題目

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. 描述過程（ Think out aloud）

當找到想要的目標，就顯示我的答案，如果數列沒有我的目標就顯示 -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;
};

使用 Binary Search 的關鍵

1. 排序後的數組
2. 限定時間複雜度的搜尋法(題目限定 O(n)以下的解法）
3. Others

補充

• 用二元搜尋,每次都要先 Sorted Array。因此追加資料時，必須插入恰當的位置，需要付出維護陣列的代價。
• 線性搜尋，陣列的數據雜亂無章也無所謂。

各種排序比較

Huli

Csdn

python