day1 二分查找 26.9.15

[数组] 704. 二分查找 / Easy / ⚠️

题目:

卡点：

1. 刚开始不知道什么是时间复杂度

• O(1)：极快。无论多少数据，瞬间完成。比如：print(nums[0])（只要数组非空，访问第一个元素）。

• O(log n)：非常快。每次操作都能排除一半的数据。比如：你正在写的二分查找。

• O(n)：一般。数据量有多大，就要操作多少次。比如：for i in range(len(nums)): 遍历数组。

• O(n log n)：稍慢。通常是高效排序算法（如快速排序、归并排序）的复杂度。

• O(n²)：很慢。通常是双重循环嵌套。数据量 100 就要操作 10000 次。比如：for i in nums: for j in nums:

2. 知道要怎么二分后卡在了不知道怎么判断结束循环,后面确实想到一种解答(通过elif验证以退出循环)但不够简洁

3. 在明白后关注到return就是一个函数的结束标志,不需要考虑太多,循环内但凡触发了return语句循环自动结束了

核心套路：

• 定义区间为 [left, right]（左闭右闭），则 while 用 left <= right

• 每次 middle = left + (right - left) // 2，避免溢出（C/Java 里更要注意）

• 如果 nums[middle] > target，说明目标在左半，right = middle - 1

• 如果 nums[middle] < target，目标在右半，left = middle + 1

• 退出循环后没找到，返回 -1

代码：

▼
Python
复制代码
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left,right = 0,len(nums)-1
        middle = left + right
        while left <=right:
            middle = (left + right)//2
            if nums[middle] == target:
                return middle
            #注意在函数中出现了return则代表着这个函数结束了输出了对应的值          
            elif nums[middle] < target:
                left = middle+1
            elif nums[middle] > target:
                right = middle-1
        return -1

复杂度：时间 O(log n)，空间 O(1)

二刷记录：

• [ ]