3.LeetCode刷题For Swift·35. Search

1、原题

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.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

2、思路

3、代码

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        // 这个题目还是使用二分法，与704题一样，只是注意下返回值就行
        // 先定义有序数组的两个边界，当前定义的是左闭右闭[left, right]
        var left = 0
        var right = nums.count - 1
        // 所以下面的循环条件就是 <= 
        while left <= right {
            // 初始化中间值，使用这种方式，防止大值溢出
            let middle = left + ((right - left) >> 1)
            if nums[middle] == target {
                return middle
            } else if nums[middle] < target {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        // 目标值没有在原数组中，并且大于最右边界
        return right + 1
    }
}