Leetcode

Leetcode 704 Binary Search

題目

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

comments powered by Disqus