InterviewQuery/target-value-search.py at main · pathankhansalman/InterviewQuery · 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
def target_value_search(rotated_input, target_value):
    if len(rotated_input) <= 2:
        return rotated_input.index(target_value)
    left = 0
    right = len(rotated_input) - 1
    pivot_idx = -1
    while 1:
        if right - left <= 1:
            if rotated_input[left] > rotated_input[right]:
                pivot_idx = left
            pivot_idx = right
            break
        mid = (left + right) // 2
        if rotated_input[mid] < rotated_input[mid - 1]:
            pivot_idx = mid - 1
            break
        elif rotated_input[mid] > rotated_input[mid + 1]:
            pivot_idx = mid
            break
        else:
            if rotated_input[left] > rotated_input[mid]:
                right = mid
            else:
                left = mid
    # print(pivot_idx)
    if pivot_idx == 0 or pivot_idx == len(rotated_input) - 1:
        if target_value == rotated_input[0]:
            return 0
        left = 1
        right = len(rotated_input) - 1
        while 1:
            if right - left <= 1:
                if rotated_input[left] == target_value:
                    return left
                elif rotated_input[right] == target_value:
                    return right
                return -1
            mid = (left + right) // 2
            if rotated_input[mid] == target_value:
                return mid
            elif rotated_input[mid] > target_value:
                right = mid
            else:
                left = mid
    else:
        left = 0
        right = pivot_idx
        while 1:
            if right - left <= 1:
                if rotated_input[left] == target_value:
                    return left
                elif rotated_input[right] == target_value:
                    return right
                break
            mid = (left + right) // 2
            if rotated_input[mid] == target_value:
                return mid
            elif rotated_input[mid] > target_value:
                right = mid
            else:
                left = mid
        left = pivot_idx + 1
        right = len(rotated_input) - 1
        while 1:
            if right - left <= 1:
                if rotated_input[left] == target_value:
                    return left
                elif rotated_input[right] == target_value:
                    return right
                return -1
            mid = (left + right) // 2
            if rotated_input[mid] == target_value:
                return mid
            elif rotated_input[mid] > target_value:
                right = mid
            else:
                left = mid