算法面試套路｜二分查找（Binary Search）

本篇內容主要為 Grokking the Coding Interview: Patterns for Coding Questions 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。

重點整理

• 二分查找（Binary Search）
• 策略：
• 題型：
  • 排序陣列

題目匯總

• 0704 Binary Search
• 0744 Find Smallest Letter Greater Than Target

[例題] Order-agnostic Binary Search

問題

給定一個已排序的整數陣列，查找給定 key 值是否存在於陣列中；但是題目並未告知排序是以升序排列或是降序排列，並且陣列中可能存在重複值。

撰寫一個函數，若 key 值存在於陣列中，返回其索引，否則返回 -1。

Example 01

Input  : arr = [4, 6, 10], key = 10
Output : 2

Example 02

Input  : arr = [1, 2, 3, 4, 5, 6, 7], key = 5
Output : 4

Example 03

Input  : arr = [10, 6, 4], key = 10
Output : 0

Example 04

Input  : arr = [10, 6, 4], key = 4
Output : 2

題解

為了讓事情更為簡單一些，首先我們假設輸入的陣列為升序排列，使用 二分查找（binary search） 的具體步驟如下：

1. 假設 start 指向陣列中的第一個元素，而 end 指向陣列中的最後一個元素，即：
   ​​​​int start = 0;
   ​​​​int end = arr.length - 1;
   

2. 透過 start 與 end 獲取 middle。在 Java 和 C++ 中，在大多數的狀況下可以透過
   $\text{middle}=\text{(start + end)}/2$ 獲得，但是當 start 或 end 較大時可能會發生整數溢位（integer overflow）。因此建議採用以下的方式更加安全：
   ​​​​middle = start + (end - start)/2
   

3. 接著我們檢查 key 是否與 middle 所指向的元素相等，如果相等就返回索引值 middle。
4. 如果 key 與 middle 所指向的元素不相等，則需要確認兩件事：
   • 如果 key < arr[middle]，我們可以得知在升序陣列中的 key 小於索引值 middle 後的所有元素，我們將查找範圍變更為 end = mid - 1
   • 如果 key > arr[middle]，我們可以得知在升序陣列中的 key 大於索引值 middle 後的所有元素，我們將查找範圍變更為 start = mid + 1
5. 獲取新的 start 與 end 並重複執行上述 (2)-(4) 的步驟，當 start 大於 end 時，表示我們無法於陣列中找到對應的 key 值，此時返回 -1。

以範例 2 為例，執行過程如圖所示：

1. 初始狀態

2. key > arr[middle]，因此 start = middle + 1

3. key < arr[middle]，因此 end = middle - 1

如果陣列為降序排列，則需要調整上述步驟 (4) 如下：

• 如果 key > arr[middle]，我們可以得知在降序陣列中的 key 大於索引值 middle 後的所有元素，我們將查找範圍變更為 end = mid - 1
• 如果 key < arr[middle]，我們可以得知在降序陣列中的 key 小於索引值 middle 後的所有元素，我們將查找範圍變更為 start = mid + 1

那麼要如何得知陣列是以升序排列還是降序排列呢？我們可以透過 arr[start] < arr[end] 進行判斷。

代碼

C++

class BinarySearch {
 public:
  static int search(const vector<int>& arr, int key) {
    int start = 0;
    int end = arr.size() - 1;
    bool isAscending = arr[start] < arr[end];
                                             
    while (start <= end) {
      int mid = start + (end - start) / 2;
      
      if (key == arr[mid]) return mid;
  
      if (isAscending) {
        if (key < arr[mid]) end = mid - 1;
        else start = mid + 1;
      } else {
        if (key > arr[mid]) end = mid - 1;
        else start = mid + 1;
      }
    }
  
    return -1;
  }
}

Java

class BinarySearch {
  public static int search(int[] arr, int key) {
    int start = 0;
    int end = arr.length - 1;
    boolean isAscending = arr[start] < arr[end];
    
    while (start <= end) {
      // calculate the middle of the current range
      int mid = start + (end - start) / 2;
      
      if (key == arr[mid]) return mid;
      
      if (isAscending) {
        if (key < arr[mid]) end = mid - 1;
        else start = mid + 1;
      } else {
        if (key > arr[mid]) end = mid - 1;
        else start = mid + 1;
      }
    }
    
    return -1;
  }
}

JavaScript

const binarySearch(arr, key) => {
  let start = 0;
  let end = arr.length - 1;
  let isAscending = arr[start] < arr[end];
  
  while (start <= end) {
    let mid = Math.floor(start + (end - start) / 2);
  
    if (key === arr[mid]) return mid;
  
    if (isAscending) {
      if (key < arr[mid]) end = mid - 1;
      else start = mid + 1;
    } else {
      if (key > arr[mid]) end = mid - 1;
      else start = mid + 1;
    }
  }
  
  return -1;
}

Python

def binary_search(arr, key):
    start = 0
    end = len(arr) - 1
  
    while start <= end:
        mid = start + (end - start) // 2

        if key == arr[mid]:
            return mid
                  
        if isAscending:
            if key < arr[mid]:
                end = mid - 1
            else:
                start = mid + 1
        else:
            if key > arr[mid]:
                end = mid - 1
            else:
                start = mid + 1
  
    return -1

分析

• 時間複雜度：
  $\mathcal{O}(\log n)$
• 空間複雜度：
  $\mathcal{O}(1)$

[例題] Ceiling of a Number

問題

給定一個按照升序排列的整數陣列，找到 key 的天花板數（Ceiling Number），亦即給定陣列中，大於或等於 key 的最小元素。

撰寫一個函數，若滿足要求的天花板數存在於陣列中，返回其索引，否則返回 -1。

Example 01

Input  : arr = [4, 6, 10], key = 6
Output : 1

Example 02

Input  : arr = [1, 3, 8, 10, 15], key = 12
Output : 4

Example 03

Input  : arr = [4, 6, 10], key = 17
Output : -1

Example 04

Input  : arr = [4, 6, 10], key = -1
Output : 0

題解

這一題遵循 二分查找（Binary Search） 策略。我們可以採取類似 Order Agnostic Binary Search 一題中的處理方式，嘗試在陣列中搜索 key 值，如果能夠找到 key 值則直接返回；如果無法找到 key 值，下一個更大的數字將由 start 指出。

以範例 2 為例，執行過程如圖所示：

1. 初始狀態

2. key > arr[middle]，因此 start = middle + 1

3. key < arr[middle]，因此 start = middle + 1

由於我們不斷調整範圍來查找 key 值，當迴圈結束時，範圍的起始位置便指向了陣列中大於 key 值的最小數字。除此之外，我們可以在最一開始添加一個判斷，檢查 key 是否大於陣列中的最大數字。

代碼

C++

class CeilOfANumber {
 public:
  static int searchCeilingOfANumber(const vector<int>& arr, int key) {
    if (key > arr[arr.size() - 1]) return -1;
  
    int start = 0;
    int end = arr.size() - 1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (key < arr[mid]) {
        end = mid - 1;
      } else if (key > arr[mid]) {
        start = mid + 1;
      } else {
        return mid;
      }
    }
  
    return start;
  }
}

Java

class CeilingOfANumber {
  public static int searchCeilingOfANumber(int[] arr, int key) {
    if (key > arr[arr.length - 1]) return -1;
  
    int start = 0;
    int end = arr.length - 1;
  
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (key < arr[mid]) {
        end = mid - 1;
      } else if (key > arr[mid]) {
        start = mid + 1;
      } else {
        return mid;
      }
    }
  
    return start;
  }                                   
}

JavaScript

const searchCeilingOfANumber(arr, key) => {
  const n = arr.length;
  if (key > arr[n - 1]) return -1;
  
  let start = 0;
  let end = n - 1;
  while (start <= end) {
    mid = Math.floor(start + (end - start) / 2);
    if (key < arr[mid]) {
      end = mid - 1;
    } else if (key > arr[mid]) {
      start = mid + 1;
    } else {
      return mid;
    }
  }
  
  return start;
}

Python

def search_ceiling_of_a_number(arr, key):
    n = len(arr)
    if key > arr[n - 1]:
        return -1
  
    start, end = 0, n - 1
    while start <= end:
        mid = start + (end - start) // 2
        if key < arr[mid]:
            end = mid - 1
        elif key > arr[mid]:
            start = mid + 1
        else:
            return mid
  
    return start

分析

• 時間複雜度：
  $\mathcal{O}(\log n)$
• 空間複雜度：
  $\mathcal{O}(1)$

[例題] Next Letter

問題

給定一個以升序排序的小寫字元陣列，找出其中大於給定 key 值的最小字母。假設給定的陣列為一個 循環列表（circular list），也就是說最後一個字母將與第一個字母相連；這也代表陣列中最小的字母，若大於陣列中最後一個字母的同時，將會是陣列中的第一個字母。

撰寫一個函數，找出給定 key 的下一個字母。

Example 01

Input  : arr = ['a', 'c', 'f', 'h'], key = 'f'
Output : 'h'

Example 02

Input  : arr = ['a', 'c', 'f', 'h'], key = 'b'
Output : 'c'

Example 03

Input  : arr = ['a', 'c', 'f', 'h'], key = 'm'
Output : 'a'

Example 04

Input  : arr = ['a', 'c', 'f', 'h'], key = 'h'
Output : 'a'

題解

這一題遵循 二分查找（Binary Search） 策略。我們可以採取類似 Ceiling of A Number 一題中的處理方式，但要考慮以下不同處：

1. 陣列視作循環列表，這代表如果 key 值大於陣列中的最後一個字母，或者小於陣列中的第一個字母，則 key 的下一個字母即為陣列中的第一個字母。
2. 我們必須找到的是 key 的下一個字母（不能與 key 相同），這代表需要忽略 key == arr[middle] 的狀況，為了處理這樣的情形，我們將更新範圍異動為 start = middle + 1。

最後，我們返回的字母將透過 start % arr_length 訪問而非 start；如同上述第 (2) 點所討論的，比如最後一個字母恰好等於 key，此時我們需要返回的會是陣列中的第一個字母。

代碼

C++

class TwoSingleNumbers {
 public:
  static vector<int> findSingleNumbers(vector<int> &nums) {
    // get the XOR of all numbers
    int n1xn2 = 0;
    for (int num : nums) n1xn2 ^= num;
    
    // get the rightmost bit that is '1'
    int rightmostSetBit = 1;
    while ((rightmostSetBit & n1xn2) == 0) rightmostSetBit = rightmostSetBit << 1;
    
    int num1 = 0;
    int num2 = 0;
    for (int num : nums) {
      if ((num & rightmostSetBit) != 0) num1 ^= num;
      else num2 ^= num;
    }
    
    return vector<int> {num1, num2};
  }
}

Java

class NextLetter {
  public static char searchNextLetter(char[] letters, char key) {
    int n = letters.length;
    if (key < letters[0] || key > letters[n - 1]) return letters[0];
  
    int start = 0;
    int end = n - 1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (key < letters[mid]) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
  
    return letters[start % n];
  }  
}

JavaScript

const searchNextLetter(letters, key) => {
  const n = letters.length;
  if (key < letters[0] || key > letters[n - 1]) return letters[0];
  
  let start = 0;
  let end = n - 1;
  while (start <= end) {
    let mid = Math.floor(start + (end - start) / 2);
    if (key < letters[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  
  return letters[start % n];
}

Python

def search_next_letter(letters, key):
    n = len(letters)
    if key < letters[0] or key > letters[n - 1]:
        return letters[0]
  
    start, end = 0, n - 1
    while start <= end:
        mid = start + (end - start) // 2
        if key < letters[mid]:
            end = mid - 1
        else:
            start = mid + 1
  
    return letters[start % n]

分析

• 時間複雜度：
  $\mathcal{O}(\log n)$
• 空間複雜度：
  $\mathcal{O}(1)$

參考資料

• Coding Patterns: Modified Binary Search | emre.me