Algorithem_BinarySearch

2022-04-12

Algorithem_BinarySearch

BinarySearch

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Constraints:
All the integers in nums are unique.
nums is sorted in ascending order.

解法

一开始我的想法是，从每次数组的中间 middleIndex 开始查找，比较数组中间的数字和 target 的大小，target 大则取从middleIndex到数组结尾截取数组生成新的数组；target 小则取从0到 middleIndex 的生成新的数组；相等则直接返回 index；然后用新生成的数组再比较，递归调用自身；但这种方法，每次递归需要记录递归开始的位置，然后最后查找到的时候，才能用查找到的 index加或减开始的位置。

官方算法：

从数组中间开始查找，声明 left、right 代表要查找的数组起始位置和结束位置
使用 while，left <= right为条件，然后遍历
- middleIndex = left + (right - left) / 2
- target < middleNum，则说明 targert 在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

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the 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 = Good, B = Bad
 |       |       |
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 = Good, B = Bad
 |       |       |
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

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

解法

这个解法和 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
    }
}