力扣刷题Day 70：在排序数组中查找元素的第一个和最后一个位置（34）

1.题目描述

2.思路

方法1（自己写的）：一次二分查找找到等于target的一个元素索引axis，然后向左右延伸找边界。

方法2（灵茶山艾府佬的闭区间二分查找写法）：定义一个lower_bound()函数找到第一个大于等于某数的元素索引，分别对target和(target + 1)调用lower_bound()函数即可。

方法3（对方法2的自主延伸）：两次二分查找，分别找小于等于(target - 1)的元素索引以及大于等于(target + 1)的元素索引。

3.代码（Python3）

方法1：

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:left, right = 0, len(nums) - 1axis = -1while left <= right:mid = (left + right) // 2if target < nums[left] or target > nums[right]: breakelif nums[mid] < target < nums[right]: left = mid + 1elif nums[left] < target < nums[mid]: right = mid - 1else:if target == nums[left]: axis = leftelif target == nums[right]: axis = rightelse: axis = midbreakif axis == -1: return [-1, -1]left_bound, right_bound = axis, axislb_found, rb_found = False, Falsewhile not lb_found or not rb_found:if not lb_found:if left_bound == 0 or nums[left_bound - 1] != target: lb_found = Trueelse: left_bound -= 1if not rb_found:if right_bound == len(nums) - 1 or nums[right_bound + 1] != target: rb_found = Trueelse: right_bound += 1return [left_bound, right_bound]

方法2：

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def lower_bound(target_num):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] >= target_num: right = mid - 1else: left = mid + 1return leftstart = lower_bound(target)if start == len(nums) or nums[start] != target: return [-1, -1]end = lower_bound(target + 1) - 1return [start, end]

方法3：

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def lower_bound(target_num):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] >= target_num: right = mid - 1else: left = mid + 1return leftdef higher_bound(target_num):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] <= target_num: left = mid + 1else: right = mid - 1 return rightstart = lower_bound(target)if start == len(nums) or nums[start] != target: return [-1, -1]end = higher_bound(target)return [start, end]

4.执行情况

方法1：

方法2：

方法3：

5.感想

其实方法3完全就是多此一举，是非常没有必要的。灵神的方法也太妙了。