Eisen 筆記

#704. Binary Search

題目描述

給你一個由小到大排序的整數陣列nums，以及整數target。
寫一個函式在nums裡尋找target。如果target存在則回傳它在整數中的位置，反之回傳-1。
演算法的時間複雜度必須為O(log n)。

限制條件

  1. 1 <= nums.length <= 10^4
  2. -10^4 < nums.length < 10^4
  3. 陣列中的所有整數都是唯一的。
  4. 陣列nums是由小排到大的。
  5. 演算法的時間複雜度必須為O(log n)。

解題思路

Brute Force

直覺做法就是從第一個檢查到最後一個，找到target，但是在最壞的情況下需要檢查完整個陣列，時間複雜度為O(n)，因此不符合限制條件。

public class Solution {
    public int Search(int[] nums, int target) {
        for(int i=0;i<nums.Length;i++){
          if(nums[i]===target) return i;
        }
        return -1;
    }
}

複雜度分析：

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)

要在整理後有序的陣列中尋找一個目標值，不需要像上面的解法一一檢查每一個元素，我們可以透過刪去法排除可能的選擇之外的大部分元素。
假設今天有一個陣列[1,2,3,4,5,6,7,8,9,10]，而目標是10，那麼我們先檢查陣列最中間的元素6，因為元素的數值是6，而陣列又是由小排到大的，因此我們可以知道6的左邊全部都是比6小的數值，目標的10不可能在那個區塊，刪去那個不要的區塊後，我們就剩下[6,7,8,9,10]，5個元素可以檢查。
接著一樣取中間的元素，這次是8，可以知道8的左手邊不會有目標存在，刪去後剩下[8,9,10]可以選擇。接著就只需要重複這個步驟直到找到目標為止。
按照上一個演算法檢查這個陣列，需要檢查10次才能找到目標值，而刪去法只需要檢查4次就能夠找到目標值，大幅增加了執行的速度。

步驟：

  1. 宣告左右指標left、right。
  2. 中間位置會等於(left + right)/2。
  3. 檢查中間位置的數值，判斷是否為目標，是則回傳位置，反之則判斷比目標大或者小。
  4. 排除不可能的區間，繼續檢查剩下可能的區間，直到找到目標為止。
public class Solution {
    public int Search(int[] nums, int target) {
        int left=0;
        int right=nums.Length-1;        
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]>target){
                right = mid-1;
            }else if(nums[mid]<target){
                left = mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}

複雜度分析：

  • 時間複雜度：每一次都排除一半的選項，時間複雜度為O(log n)。
  • 空間複雜度：O(1)。

學習重點

  • Binary Search的特性。
  • Binary Search的應用。
Last Updated:
Contributors: eisen