题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题解

如果修改下题目要求，不要求返回给定值的第一个(开始位置)、最后一个(结束位置)，只要等于给定的值就返回，那会变成什么样呢？
假设给定的数组如下图所示，给定的值是3，求下标。

上图的数组中下标2，3，4，5，6都满足要求，返回任意一个都可以了。
这个查找过程用正常的二分查找就可以满足:

def binary_search(nums):
	if not nums:
		return -1
	begin = 0
	end = len(nums)-1
	while begin<=end:
		mid = begin+(end-begin)//2
		if nums[mid]>target:
			end = mid-1
		elif nums[mid]<target:
			begin = mid+1
		else:
			return mid
	return -1

如果对二分查找没有印象了，可以参考这篇文章回忆一下。
现在我们再把题目的要求加上，已经定位到3这个元素了，如果求得第一个3和最后一个3出现的位置呢？
如果直接挨个向前移动查找，或者挨个向后移动查找是不行的。

题目要求了时间复杂度是O(logN)，挨个查找的话，时间复杂度就变成O(N)了，而且这么查找的话，跟从头到尾扫描一遍也没区别，那么就必须用更高的效率找到第一个和最后一个元素。

到这里，我们就有一个大致的脉络了

1. 首先用正常的二分查找定位到给定的元素，时间复杂度O(logN)
2. 在定位到指定元素的情况下，用O(logN)时间复杂度查找第一个/最后一个

第一点题我们已经解决了，现在看看如何解决第二点。
怎么样才算找到第一个目标值呢？

很简单，当nums[i]等于nums[i-1]时，说明nums[i]肯定不是第一个，那么继续缩小右边界，往左边查找。直到不满足条件时，此时就找到了第一个给定值。
但还有一个特殊情况，nums[i]的下标为0时，这也很好理解，前面都没元素了，那当前元素肯定就是第一个了。

对于最后一个元素也是类似的

如果nums[i]等于nums[i+1]就增大左边界，往右边查找，直到不满足条件，此时就找到了最后一个给定值。
如果nums[i]的下标是len(nums)-1，那也不用找了。

至此，我们就实现了完整的查找逻辑了

def binary_search(nums):
	if not nums:
		return -1
	begin = 0
	end = len(nums)-1
	while begin<=end:
		mid = begin+(end-begin)//2
		if nums[mid]>target:
			end = mid-1
		elif nums[mid]<target:
			begin = mid+1
		else:
			# 找到目标值了，开始查找第一个目标值
			if mid>0 and nums[mid]==nums[mid-1]:
				end = mid-1
			else:
				return mid
	return -1
                                                                   

详细说明下上面代码中else中的这段:

if mid>0 and nums[mid]==nums[mid-1]:
	end = mid-1
else:
	return mid

既然找到了目标值，就将当前值和前一个值对比，如果一样说明没找到，那么就需要缩小右边界。
缩小右边界的原因是我们要找第一个，第一个肯定是在最左边，所以就要缩小右边界。

下面演示查找第一个目标值的过程(目标值是3):

接着是查找最后一个目标值的过程(目标值是3):

java代码:

class Solution {
	public int[] searchRange(int[] nums, int target) {
		if(nums==null) {
			return new int[]{-1,-1};
		}
		int firstIndex = find(true,nums,target);
		int lastIndex = find(false,nums,target);
		return new int[]{firstIndex,lastIndex};
	}
	
	//查找第一个和最后一个元素
	private int find(boolean isFindFirst,int[] nums,int target) {
		int begin = 0;
		int end = nums.length-1;
		//if和else if的逻辑跟正常的二分查找一样
		while(begin<=end) {
			int mid = begin+(end-begin)/2;
			if(nums[mid]>target) {
				end = mid-1;
			}
			else if(nums[mid]<target) {
				begin = mid+1;
			}
			//找到目标值了，开始定位到第一个和最后一个位置
			else {
				//查找第一个和最后一个逻辑很类似，这里用一个变量标记
				//是查找第一个还是查找最后一个
				if(isFindFirst) {
					//如果不满足条件，缩小右边界，继续往左边查找
					if(mid>0 && nums[mid]==nums[mid-1]) {
						end = mid-1;
					} else {
						return mid;
					}
				}
				else {
					//如果不满足条件，增大左边界，继续往右边查找
					if(mid<nums.length-1 && nums[mid]==nums[mid+1]) {
						begin = mid+1;
					} else {
						return mid;
					}
				}
			}
		}
		return -1;
	}
}
                                                                                             

python代码:

class Solution(object):
	def searchRange(self, nums, target):
		if not nums:
			return [-1,-1]
		n = len(nums)
		# 查找第一个和最后一个元素
		def find(is_find_first):
			begin = 0
			end = n-1
			# if和elif的逻辑跟正常的二分查找一样
			while begin<=end:
				mid = begin+(end-begin)/2
				if nums[mid]>target:
					end = mid-1
				elif nums[mid]<target:
					begin = mid+1
				# 找到目标值了，开始定位到第一个和最后一个位置	
				else:
					# 查找第一个和最后一个逻辑很类似，这里用一个变量标记
					# 是查找第一个还是查找最后一个
					if is_find_first:
						# 如果不满足条件，缩小右边界，继续往左边查找
						if mid>0 and nums[mid]==nums[mid-1]:
							end = mid-1
						else:
							return mid
					else:
						# 如果不满足条件，增大左边界，继续往右边查找
						if mid<n-1 and nums[mid]==nums[mid+1]:
							begin = mid+1
						else:
							return mid
			return -1
		return [find(True), find(False)]
                                                                                             

(全文完)

20 次阅读