leet/range.py at master · yuyue9284/leet · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
__author__ = 'yuyue'


def search(nums, target, i, j, start, stop):
    middle = (i + j) / 2
    if j - i > 1:
        if nums[middle] > target:
            search(nums, target, i, middle, start, stop)
        elif nums[middle] < target:
            search(nums, target, middle, j, start, stop)
        elif nums[middle] == target:
            if middle < start[0]:
                start[0] = middle
            if middle > stop[0]:
                stop[0] = middle
            search(nums, target, i, middle, start, stop)
            search(nums, target, middle, j, start, stop)
    else:
        if nums[j] == target:
            if j > stop[0]:
                stop[0] = j
        if nums[i] == target:
            if i < start[0]:
                start[0] = i


nums = [1, 3, 4, 5, 6, 7]

start = [len(nums)]
stop = [-1]

search(nums,4,0,start[0]-1,start,stop)

print start
print stop