今是昨非

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#

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#

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
    }
}