Chia-ch'i

The primary purpose of this website is to motivate me to write about life, thoughts, and learning observations.

2025-06-03 lc704. Binary Search

date: 2025-06-03 name: aliases: tags:

  • leetcode
  • python
  • BinarySearch date_last_edit: 2025-06-03 16:46 —

    2025-06-03

— creation date: 2025-06-03 16:40 — modification date: 星期二 3 日六月 2025 16:46:06

704. Binary Search

这里是最简单的二分搜索, 就 follow acwing 的按照写 check 函数的方法来写这个部分就 OK, 然后开始思考, 这里写完后, 针对我的一直在犯错的地方有我老是忘记 while 中的 if 到底在变什么, 这个题目一开始学的时候, 我感觉很难, 但是现在我感觉写的时候, 脑子已经没有在动了, 所以要提醒自己, 这里要思考的位置, 就是在 if 循环下, 这里要判断并且记住是什么要动. OK, 开始写代码, 这里不要使用三个 if 的那个想法, 因为那个其实是特殊模版, OK, 然后, 开始写, 空白代码如下,

class Solution:
    def search(self, nums: List[int], target: int) -> int:

现在应该要怎么办, OK, 常理上可以直接想到要有 left 和 right, 什么是我们的 left 和 right

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

这里注意摒弃各种左闭右开, 左闭右闭的乱七八糟的想法和思路, 都是思考负担, 从实际含义出发, 这里的 left 和 right 都是原始的索引上可以看到的数字, 那么接下来是我们的 while 循环,

while left < right: # while条件判断left和right相等停止, index角度避免越界
	mid = (left + right) // 2 # mid = (right - left) // 2 + left // 2

开始想 if 条件判断, 这里的时候注意 从我们想找什么的实际意义出发, sorted in ascending order nums, write a function to search target , If target exists, then return its index OK, 那么看完这个已经很明显了, check 函数可以写成如下两个

  1. 找找现在的数是大于等于当前的 target 吗
  2. 找找现在的数是小于等于当前的 target 吗 这里的 check 函数都是有这个等于的情况的, 因为我们的题意中就是让我们找到一个等于的值 那么, 其实就很好写了
比较的时候我们永远拿的是 mid 这个 index 量来比较, 所以想象什么要变?

第一种方法

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
	 		mid = (left + right) // 2
	 		if nums[mid] >= target:
				right = mid # no mid - 1, cuz of missing the "==" idx
			else: # nums[mid] < target:
				left = mid + 1 # cuz wanna find the correct idx  
		return -1 if nums[left] != target else left # or right

第二种方法

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
	 		mid = (left + right + 1) // 2
	 		if nums[mid] <= target:
				left = mid # wanna keep the last correct idx
			else: 
				right = mid - 1
		return -1 if nums[left] != target else left # or right

思考 :(使用 deepseek- R1(元宝 25-06-03)输出回答) 留一个坑以后补

1.回忆 acwing 的方法中, 为什么 left = mid 的情况, 我们就要改变取 mid 的方法 to mid = (left + right + 1) // 2

在二分查找中，边界调整与mid计算方式密切相关，主要为了避免死循环。当出现 left = mid 时，如果mid采用向下取整（普通mid计算），在特定情况下（如left和right相邻）会导致死循环。因此需要将mid计算改为向上取整（即 (left + right + 1) // 2）来避免这种情况。

2.如何用递归来写这个问题呢?

注意需要传递什么输入参数(不要输入创建一个新的 nums arr)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return self._binary_search_recursive(nums, target, 0, len(nums)-1)
    
    def _binary_search_recursive(self, nums: List[int], target: int, left: int, right: int) -> int:
        # 终止条件1：区间无效（未找到）
        if left > right:
            return -1
        mid = (left + right) // 2  # 普通取整（因后续递归会严格缩小区间）
        # 终止条件2：找到目标
        if nums[mid] == target:
            return mid
        # 目标在右半区
        elif nums[mid] < target:
            return self._binary_search_recursive(nums, target, mid+1, right)
        # 目标在左半区
        else:
            return self._binary_search_recursive(nums, target, left, mid-1)

3.在代码随想录中的思考题 lc35.搜索插入位置 lc34.在排序数组中查找元素的第一个和最后一个位置 上面两题反复做过了, 等两天复健一下, 写两篇思路过程出来

2025

2025-06-03 lc704. Binary Search

4 minute read

date: 2025-06-03 name: aliases: tags: leetcode python BinarySearch date_last_edit: 2025-06-03 16:46 — 2025-06-03

Back to top ↑

2024

Back to top ↑

2023

Back to top ↑