简介

题目：

有序且可重复的整型数组（数据量会很大），查询数据项，返回匹配的子数组索引范围 ，要求时间复杂度 O(logn) ，下面是测试用例：

xxxxxxxxxx
arr = [1,2,3,4,4,4,6,7] 
target = 4 
result = [3, 5] 
​
target = 1 
result = [0, 0] 
​
target = 8 
result = [-1, -1]

思路：

先用二分查找找到目标元素，然后再分别用二分查找定位左边界和右边界。

Python 实现

xxxxxxxxxx
#coding=utf-8
​
​
def binary_search(arr, target, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
​
    while low <= high:
        mid = (low + high) / 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            low = mid + 1
        else:
            high = mid - 1
​
    return -1
​
​
def find_pos(arr, target):
    low = 0
    high = len(arr) - 1
    pos = binary_search(arr, target, low, high)
    if pos == -1:
        return -1, -1
​
    temp = left = pos
    while temp != -1:
        left = temp
        if temp == 0:
            break
        temp = binary_search(arr, target, low, left - 1)
​
    temp = right = pos
    while temp != -1:
        right = temp
        if temp == high:
            break
        temp = binary_search(arr, target, temp + 1, high)
​
    return left, right
​
​
if __name__ == "__main__":
    arr = [1,2,3,4,4,4,6,7]
    target = 4
    print(find_pos(arr, target))
​