算法_二分搜尋 - 今是昨非

Algorithem_BinarySearch#

BinarySearch#

給定一個按升序排列的整數數組 nums 和一個整數 target，編寫一個函數在 nums 中查找 target。如果 target 存在，則返回其索引。否則，返回 -1。

你必須編寫一個 O (log n) 時間複雜度的算法。

約束條件：
nums 中的所有整數都是唯一的。
nums 是按升序排列的。

解法#

一開始我的想法是，從每次數組的中間 middleIndex 開始查找，比較數組中間的數字和 target 的大小，target 大則取從 middleIndex 到數組結尾截取數組生成新的數組；target 小則取從 0 到 middleIndex 的生成新的數組；相等則直接返回 index；然後用新生成的數組再比較，遞歸調用自身；但這種方法，每次遞歸需要記錄遞歸開始的位置，然後最後查找到的時候，才能用查找到的 index 加或減開始的位置。

官方算法：

從數組中間開始查找，聲明 left、right 代表要查找的數組起始位置和結束位置
使用 while，left <= right 為條件，然後遍歷
- middleIndex = left + (right - left) / 2
- target < middleNum，則說明 target 在 left 到 middle-1 之間；
- target > middleNum，則說明 target 在 middle + 1 到 right 之間；
- target == middleNum，則直接返回 middleIndex 即可。

邊界值測試：

如果有一個元素，則，left=0，right=0，left=right，middleIndex=0，判斷 nums [middleIndex] 是否等於 target
如果有兩個元素，則，left=0，right=1，left<right，middleIndex=0，判斷 nums [middleIndex] 和 target 大小
- 如果 target <nums [middleIndex]，right = middleIndex-1=-1，left > right，不滿足循環條件，說明數組沒有此元素，返回 -1
- 如果 target > nums [middleIndex]，left = middleIndex+1=1，left = right，繼續遍歷下一次，left=1，right=1，middleIndex=1，判斷 nums [middleIndex] 和 target 大小
- 如果 target = nums [middleIndex]，則返回 middleIndex 即可。

代碼如下：


class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        let count = nums.count
        
        var left = 0
        var right = count - 1
        var findIndex = 0
        
        while (left <= right) {
            findIndex = left + (right - left) / 2
            
            let num = nums[findIndex]
            if target < num {
                right = findIndex - 1
            }
            else if target > num {
                left = findIndex + 1
            }
            else {
                return findIndex
            }
        }
        return -1
    }
}

FirstBadVersion#

你是一名產品經理，目前正在帶領一個團隊開發一個新產品。不幸的是，你的產品最新版本未通過質量檢查。由於每個版本都是基於上一個版本開發的，因此所有壞版本之後的版本也都是壞的。

假設你有 n 個版本 [1, 2, ..., n]，你想找出第一個壞版本，這個版本導致所有後面的版本都是壞的。

你獲得了一個 API bool isBadVersion (version)，它返回版本是否是壞的。實現一個函數來查找第一個壞版本。你應該最小化對 API 的調用次數。

解法#

一開始我的想法是：類似 BinarySearch，先從中間值開始，如果中間的是 BadVersion，則繼續往前取中間；如果中間的不是 BadVersion，則繼續往後取中間。但是結束的條件，一直沒有理解清楚。

官方算法：

從數組中間開始查找，聲明 left、right 代表要查找的數組起始位置和結束位置
使用 while，left < right 為條件，然後遍歷
- middleIndex = left + (right - left) / 2
- middleIndex 是 BadVersion，則說明第一個 BadVersion 在 left 到 middleIndex 之間，這裡需要注意的是當前 middleIndex 可能是第一個 BadVersion，所以取得時需要包含 middleIndex
- middleIndex 不是 BadVersion，則說明第一個 BadVersion 在 middleIndex + 1 到 right 之間；

測試：


Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = 好的, B = 壞的
 |       |       |
left    mid    right

Scenario #1 詳解：

left=1, right=9; left <right; middle = 5, isBadVersion (5) = false，說明 5 是好的，壞的版本在 6~9 之間；把 left 賦值為 6
left=6, right=9; left <right; middle = 7, isBadVersion (7) = true，說明 7 是壞的，壞的版本在 6~7 之間；把 right 賦值為 7
left=6, right=7; left <right; middle = 6, isBadVersion (6) = false，說明 6 是好的，壞的版本在 7~7 之間；把 left 賦值為 7
left=7, right=7; left = right; 不滿足循環條件，最終 left=7，7 即是第一個壞的版本；


Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = 好的, B = 壞的
 |       |       |
left    mid    right

Scenario #2 詳解：

left=1, right=9; left <right; middle = 5, isBadVersion (5) = true，說明 5 是壞的，壞的版本在 left~5 之間；把 right 賦值為 5
left=1, right=5; left <right; middle = 3, isBadVersion (3) = false，說明 3 是好的，壞的版本在 4~right 之間；把 left 賦值為 4
left=4, right=5; left <right; middle = 4, isBadVersion (4) = true，說明 4 是壞的，壞的版本在 left~4 之間；把 right 賦值為 4
left=4, right=4; left = right; 不滿足循環條件，最終 left=4，4 即是第一個壞的版本；

代碼如下：

/**
 * The knows API is defined in the parent class VersionControl.
 *     func isBadVersion(_ version: Int) -> Bool{}
 */

class Solution : VersionControl {
    func firstBadVersion(_ n: Int) -> Int {
        var left = 1
        var right = n
        
        while left < right {
            let middle = left + (right - left) / 2
            let isBad = isBadVersion(middle) 
            if isBad {
                right = middle
            }
            else {
                left = middle + 1
            }
        }
        
        return left
    }
}

Search Insert Position#

給定一個排序的不同整數數組和一個目標值，如果找到目標則返回索引。如果沒有，則返回如果按順序插入時的索引。

你必須編寫一個 O (log n) 時間複雜度的算法。

解法#

這個解法和 BinarySearch 邏輯一樣，唯一不同的是，BinarySearch 查找不到返回 -1，而這個查找不到相等的最後返回的是 left 的位置。

代碼如下：


class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        
        var left = 0
        var right = nums.count - 1
        var middle = 0
        while left <= right {
            middle = left + (right - left) / 2
            
            let middleNum = nums[middle]
            if target < middleNum {
                // means target in left..<middle
                right = middle - 1
            }
            else if target > middleNum {
                // means targets in middle..<right
                left = middle + 1
            }
            else {
                // equal return middleNum
                return middle
            }
        }
        
        return left
    }
}