leetcode代码记录（二分查找

目录

• 1. 题目：
• 2. 我的代码：
• 小结：

1. 题目：

给定一个 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

2. 我的代码：

左闭右闭法

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

        while left_i <= right_i:
            middle_i = (left_i + right_i) // 2
            if nums[middle_i] > target:
                right_i = middle_i - 1
            elif nums[middle_i] < target:
                left_i = middle_i + 1
            else:
                return middle_i
        
        return -1

左闭右开法：

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

        while left_i < right_i:
            middle_i = (left_i + right_i) // 2
            if nums[middle_i] > target:
                right_i = middle_i
            elif nums[middle_i] < target:
                left_i = middle_i + 1
            else:
                return middle_i
        
        return -1

二分法还是比较好理解的，就相当于左右指针，并且用中间值去检查是否符合目标值。如果大于目标值，则说明右指针可以向左边靠拢；如果小于目标值，则说明左指针可以向右边靠拢。

对于左闭右闭法，即[left_i, right_i]，while里放的应当是left_i <= right_i，因为left_i == right_i时这个值也需要检查，也就是还剩下一个值需要检查。

对于左闭右开法，即[left_i, right_i)，while里放的应当是left_i < right_i，因为left_i == right_i时这个值不需要检查，左闭右开时这个区间是空。还有一个细节就是，nums[middle_i] > target时right_i = middle_i而不是middle_i - 1，不能把这个点包含进去。

小结：

关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||代码兼职|| ||代码问题求解||
添加我的公众号即可：