# 题目

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].

# 题解

• (1)寻找最左的index: 找到相等时，`high=mid`，让它一直向左走
• (2)寻找最右的index: 找到相等时，`low=mid`，让它一直向右走

# 代码

```#!/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      ```

89 篇文章41 人订阅

0 条评论

## 相关文章

26212

### 剑指Offer面试题：24.复杂链表的复制

下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向NULL的指针没有画出。

732

983

1043

### 20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1886

1192

2746

492

1023

### Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员，其中 HashMap 是 Map 接口的常用实现类，...

3970