1、原题

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

2、思路

3、代码

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        // 先定义有序数组的两个边界，当前定义的是左闭右闭[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 -1
    }
}