Data_Structure_And_Algorithm_Using_Python/binary_search1.py at master · rahult017/Data_Structure_And_Algorithm_Using_Python · 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
36
37
38
39
40
41
42
43
def binary_search(low,high,condition):
    while low <= high:
        mid = (low + high) //2
        result = condition(mid)
        if result == "Found":
            return mid
        elif result == "Left":
            high = mid - 1
        else:
            low = mid + 1
    return -1

def first_position(num,target):
    def condition(mid):
        if num[mid] == target:
            if mid > 0 and num[mid-1] == target:
                return "Left"
            return "Found"
        elif num[mid] < target:
            return "Right"
        else:
            return "Left"
    return binary_search(0,len(num)-1,condition)


def last_position(num,target):
    def condition(mid):
        if num[mid] == target:
            if mid < len(num)-1 and num[mid+1] == target:
                return "Right"
            return "Found"
        elif num[mid] < target:
            return "Right"
        else:
            return "Left"
    return binary_search(0,len(num)-1,condition)

def first_and_lsat_position(num,target):
    return first_position(num,target),last_position(num,target)

nums =[5,7,7,8,8,10]
target = 8
print(first_and_lsat_position(nums,target))