难度: Easy
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
示例 2:
输入:nums= [-1,0,3,5,9,12],target= 2 输出: -1 解释: 2 不存在nums中因此返回 -1
提示：
nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。运行时间: 248 ms
内存: 16 MB
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
return lo if len(nums)-1 >= lo >= 0 and nums[lo] == target else -1
这个题解使用了二分查找的思路。首先定义了两个指针lo和hi，分别指向数组的开始和结束位置。然后使用while循环不断缩小搜索区间，每次循环都计算中间位置mid，并比较nums[mid]和target的大小。如果相等则直接返回mid；如果nums[mid]大于target，则将搜索区间缩小到[lo, mid-1]；如果nums[mid]小于target，则将搜索区间缩小到[mid+1, hi]。循环结束后，如果lo在数组范围内且nums[lo]等于target，则返回lo，否则返回-1。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums)
while lo < hi:
# 计算中间位置
mid = lo + (hi - lo) // 2
if nums[mid] == target:
# 找到目标值，直接返回下标
return mid
elif nums[mid] > target:
# 目标值在左半部分，缩小搜索区间到[lo, mid-1]
hi = mid - 1
elif nums[mid] < target:
# 目标值在右半部分，缩小搜索区间到[mid+1, hi]
lo = mid + 1
# 循环结束后，如果lo在数组范围内且nums[lo]等于target，返回lo，否则返回-1
return lo if len(nums)-1 >= lo >= 0 and nums[lo] == target else -1
初始化`hi`为`len(nums)`（而非`len(nums) - 1`）是因为，在这种实现中，`hi`始终保持为开区间的一部分（即不包括在搜索区间内）。这样的处理简化了边界条件的处理，避免了一些常见的越界错误。此外，这种处理使得循环可以统一为`while lo < hi`，在循环内部通过调整`lo`和`hi`来缩小搜索范围，而不是担心是否漏掉了边界元素。
当`nums[mid]`大于`target`时，将`hi`设置为`mid - 1`是为了排除`mid`位置的元素（已知它不等于`target`），从而缩小搜索区间。如果将`hi`设置为`mid`，则下一次循环仍然会考虑`nums[mid]`这个已经知道不是目标的元素，这会导致不必要的重复比较并可能引起循环无法正确终止。
在二分查找的最后，`lo`可能指向的是目标值`target`应当插入的位置，而这个位置有可能不包含实际的目标值。因此，需要额外检查`lo`指向的位置是否仍在数组范围内以及这个位置的值是否确实等于`target`。这是为了确认最终没有找到目标值的情况下，返回正确的结果（比如`-1`），从而确保算法的准确性和完整性。
如果`nums`数组为空，则在算法的初始设置中，`lo`将被初始化为0，而`hi`也为0（因为`nums`长度为0）。因此，`while lo < hi`的条件立即为假，循环不会执行。最终，会执行到最后的返回语句，其中由于`lo`不满足数组范围（即不在0到-1之间），因此会返回`-1`，表示目标值在数组中不存在。