当前位置：首页 > article >正文

ARTS-01

article 2025/1/12 1:39:59

什么是ARTS？

算法(Algorithm): 每周至少一道LeetCode算法题，加强编程训练和算法学习
阅读(Review)：阅读并点评至少一篇英文技术文章，提高英文水平
技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点
分享(Share)：分析一篇有关点和思考的技术文章，建立影响力，输出价值观

算法：

题目描述：

给定一个 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]之间。

前置知识：

什么是二分查找？

二分查找（Binary Search）是一种高效的搜索算法，适用于在有序数组中查找特定元素的位置。它通过反复将搜索区间减半来快速定位目标值，从而显著减少了所需的比较次数。与线性搜索相比，二分查找的时间复杂度为 O(log⁡n)，其中 n 是数组的长度，这使得它在处理大规模数据时更加高效。

时间复杂度为 O(log⁡n)：假如n个数经过从k次减半后变为1：n, n/2, n/4, ... , 1，即n/(2^k)=1，得到k=log2(n)。

二分查找的工作原理

初始化：
- 定义两个指针 left 和 right，分别指向数组的第一个和最后一个元素。
- 这两个指针定义了当前搜索区间的边界。
迭代或递归：
- 在每次迭代或递归调用中，计算中间位置 mid，即 (left+right)//2(left+right)//2 或更优地使用 (left+(right−left)//2)(left+(right−left)//2) 来防止大数溢出。
- 比较中间位置的元素 nums[mid] 与目标值 target：
  - 如果 nums[mid] == target，则找到目标值，返回其索引。
  - 如果 nums[mid] < target，则目标值位于右半部分，更新 left = mid + 1。
  - 如果 nums[mid] > target，则目标值位于左半部分，更新 right = mid - 1。
终止条件：
- 当 left > right 时，说明搜索区间为空，此时如果还没有找到目标值，则返回 -1 表示目标值不在数组中。

思路：

由于数组已经排序，可以利用二分查找来高效地定位目标值的位置。二分查找的基本思想是不断缩小搜索区间，通过比较中间元素和目标值来进行决策：如果中间元素正好等于目标值，则返回其索引；如果中间元素小于目标值，则在右半部分继续搜索；反之，在左半部分继续搜索。当搜索区间为空时，说明数组中不存在目标值。

关键点：

数组必须是有序的。
数组中的元素不重复。
通过调整左右指针的位置来控制搜索范围。
时间复杂度为 O(log n)，其中 n 是数组的长度。

代码：

暴力解：

def search(nums, target):
    if target in nums:
        return nums.index(target)
    else:
        return -1
# 示例测试用例
print(search([-1, 0, 3, 5, 9, 12], 9))  # 输出: 4
print(search([-1, 0, 3, 5, 9, 12], 2))  # 输出: -1

暴力代码（使用 in 和 index()）：
- 时间复杂度：O(n)
- 空间复杂度：O(1)

二分查找：

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1

# 示例测试用例
print(search([-1,0,3,5,9,12], 9))  # 输出: 4
print(search([-1,0,3,5,9,12], 2))  # 输出: -1