题目
Search for a Range Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
题解
想必大家看到时间要求O(log n)，已经想到了需要使用二分查找，二分查找很简单，关键是这个题目要我们找到target的区间
其实很简单，分成两步就好了，第一次尽量向左走，第二次尽量向右走，获得左边和右边的位置，返回即可
- (1)寻找最左的index: 找到相等时，
high=mid，让它一直向左走 - (2)寻找最右的index: 找到相等时，
low=mid，让它一直向右走
代码
代码语言：javascript复制#!/usr/bin/python
# -*- coding:utf-8 -*-
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) == 0:
return [-1, -1]
start_index = self.lsearch(nums, target)
end_index = self.rsearch(nums, target)
return [start_index, end_index]
def rsearch(self, nums, target):
# 二分查找，相等时候一直向右
low = 0
high = len(nums) - 1
while low < high - 1:
mid_index = (low high) // 2
if nums[mid_index] > target:
high = mid_index - 1
elif nums[mid_index] < target:
low = mid_index 1
else:
low = mid_index
if nums[high] == target:
return high
elif nums[low] == target:
return low
else:
return -1
def lsearch(self, nums, target):
# 二分查找，一直向左走
low = 0
high = len(nums) - 1
while low < high - 1:
mid_index = (low high) // 2
if nums[mid_index] > target:
high = mid_index - 1
elif nums[mid_index] < target:
low = mid_index 1
else:
high = mid_index
if nums[low] == target:
return low
elif nums[high] == target:
return high
else:
return -1
if __name__ == '__main__':
a = Solution()
st = a.searchRange([1,8,8,8,8,9,9,10,10,10,11], 8)
print st 
