Data_Structure_And_Algorithm_Using_Python/binary_search.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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
def locate_card(cards,query):
    low, high = 0, len(cards) - 1

    # while low <= high:
    for _ in range(len(cards)):
        mid = (low + high) // 2
        result = test_locate(cards,query,mid)
        if result == "Found":
            return mid
        elif result == "Left":
            high = mid - 1
        elif result == "Right":
            low = mid+1

        # mid_number = cards[mid]

        # #print("lo:", lo, ", hi:", hi, ", mid:", mid, ", mid_number:", mid_number)

        # if mid_number == query:
        #     return mid
        # elif mid_number < query:
        #     high = mid - 1
        # elif mid_number > query:
        #     low = mid + 1

    return -1

def test_locate(cards,query,mid):
    mid_number = cards[mid]
    if mid_number == query:
        if mid -1 >= 0 and cards[mid-1] == query:
            return "Left"
        else:
            return "Found"
    elif mid_number < query:
        return "Left"
    else:
        return "Right"


cards = [13, 11, 10, 7, 4, 3, 1, 0]
query = 7
output = 3
# result = locate_card(cards,query)
# print(result)
test_data =[{'input': {'cards': [13, 11, 10, 7, 4, 3, 1, 0], 'query': 7}, 'output': 3},
 {'input': {'cards': [13, 11, 10, 7, 4, 3, 1, 0], 'query': 1}, 'output': 6},
 {'input': {'cards': [4, 2, 1, -1], 'query': 4}, 'output': 0},
 {'input': {'cards': [3, -1, -9, -127], 'query': -127}, 'output': 3},
 {'input': {'cards': [6], 'query': 6}, 'output': 0},
 {'input': {'cards': [9, 7, 5, 2, -9], 'query': 4}, 'output': -1},
 {'input': {'cards': [], 'query': 7}, 'output': -1},
 {'input': {'cards': [8, 8, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 3},
  'output': 7},
 {'input': {'cards': [8, 8, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0],
   'query': 6},
  'output': 2}]

# for test_data in test_data:
#     result1 = locate_card(**test_data['input'])
#     print(result1,test_data['output'])

#o(logn)
#o(1)


# Generic way
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 rewrite_locate_card(cards,query):
    def condition(mid):
        mid_number = cards[mid]
        if mid_number == query:
            if mid -1 >= 0 and cards[mid-1] == query:
                return "Left"
            else:
                return "Found"
        elif mid_number < query:
            return "Left"
        else:
            return "Right"
    return binary_search(0,len(cards)-1,condition)
print(rewrite_locate_card(cards,query))