---
title: "算法面試套路｜二分查找（Binary Search）"
description: "Patterns for Coding Questions: Binary Search."
image: https://i.imgur.com/dIdSDDr.png
author: Hsins
tags: LeetCode, Coding Interview
robots:
breaks:
GA:
disqus:
---
# 算法面試套路｜二分查找（Binary Search）
<p style="text-align: center">
<img src="https://i.imgur.com/dIdSDDr.png" height=200/>
</p>
> 本篇內容主要為 [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。
## 重點整理
- 二分查找（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 為例，執行過程如圖所示：
<p style="text-align: center">
<small>1. 初始狀態</small><br/>
<img src="https://i.imgur.com/775j2kr.png"><br/>
<small>2. <code>key > arr[middle]</code></small>，因此 <code>start = middle + 1</code><br/>
<img src="https://i.imgur.com/RWJkqRa.png"><br/>
<small>3. <code>key < arr[middle]</code></small>，因此 <code>end = middle - 1</code><br/>
<img src="https://i.imgur.com/KdRi7yu.png"><br/>
</p>
如果陣列為降序排列，則需要調整上述步驟 (4) 如下：
- 如果 `key > arr[middle]`，我們可以得知在降序陣列中的 `key` 大於索引值 `middle` 後的所有元素，我們將查找範圍變更為 `end = mid - 1`
- 如果 `key < arr[middle]`，我們可以得知在降序陣列中的 `key` 小於索引值 `middle` 後的所有元素，我們將查找範圍變更為 `start = mid + 1`
那麼要如何得知陣列是以升序排列還是降序排列呢？我們可以透過 `arr[start] < arr[end]` 進行判斷。
### 代碼
#### C++
``` cpp
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
``` 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
``` 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
``` 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](#例題-Order-agnostic-Binary-Search) 一題中的處理方式，嘗試在陣列中搜索 `key` 值，如果能夠找到 `key` 值則直接返回；如果無法找到 `key` 值，下一個更大的數字將由 `start` 指出。
以範例 2 為例，執行過程如圖所示：
<p style="text-align: center">
<small>1. 初始狀態</small><br/>
<img src="https://i.imgur.com/ogF6GiS.png"><br/>
<small>2. <code>key > arr[middle]</code></small>，因此 <code>start = middle + 1</code><br/>
<img src="https://i.imgur.com/kRC7W3F.png"><br/>
<small>3. <code>key < arr[middle]</code></small>，因此 <code>start = middle + 1</code><br/>
<img src="https://i.imgur.com/wgw9f4m.png"><br/>
</p>
由於我們不斷調整範圍來查找 `key` 值，當迴圈結束時，範圍的起始位置便指向了陣列中大於 `key` 值的最小數字。除此之外，我們可以在最一開始添加一個判斷，檢查 `key` 是否大於陣列中的最大數字。
### 代碼
#### C++
``` cpp
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
``` 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
``` 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
``` 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](#例題-Ceiling-of-a-Number) 一題中的處理方式，但要考慮以下不同處：
1. 陣列視作循環列表，這代表如果 `key` 值大於陣列中的最後一個字母，或者小於陣列中的第一個字母，則 `key` 的下一個字母即為陣列中的第一個字母。
2. 我們必須找到的是 `key` 的下一個字母（不能與 `key` 相同），這代表需要忽略 `key == arr[middle]` 的狀況，為了處理這樣的情形，我們將更新範圍異動為 `start = middle + 1`。
最後，我們返回的字母將透過 `start % arr_length` 訪問而非 `start`；如同上述第 (2) 點所討論的，比如最後一個字母恰好等於 `key`，此時我們需要返回的會是陣列中的第一個字母。
### 代碼
#### C++
``` cpp
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
``` 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
``` 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
``` 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](https://emre.me/coding-patterns/modified-binary-search/)
Sign in with Wallet
Connect another wallet