Binary Rotated Search with 0 and negative nums

user_18584286 0
Viewed 19

I have the binary search for pivot (max) working perfectly fine unless I add 0 or negative nums to the array provided to function

In some positions of 0 (or neg nums) the code just not returns

Can someone explains why is so??? Like this [16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] puts the code to no return I really can not get it

import random


def find_max(arr, low, high):
    while True:
        if arr[0] < arr[-1]:
            return arr[-1]
        mid = (low + high) // 2
        if arr[mid] > arr[mid + 1]:
            return arr[mid]
        if arr[mid] > arr[high]:
            low = mid + 1
        elif arr[mid] < arr[high]:
            high = mid - 1
    return None


def rotate(what):
    for _ in range(random.randint(1, len(what))):
        what.insert(0, what.pop())
    return what

arr = rotate([x for x in range(0, 20)])
print(arr)
res = find_max(arr, 0, len(arr) - 1)
print(res)
binary arrays python
1 Answers

I think there is an issue in your find_max(arr, low, high) function first if condition. I have made a change in find_max(arr, low, high) and it seems to be working.

arr = [16, 17, 18, 19,-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

def find_max(arr, low, high):
    while True:
        if arr[0] < arr[high]:
            return arr[high]
        mid = (low + high) // 2
    
        if arr[mid] > arr[mid + 1]:
            return arr[mid]
        if arr[mid] > arr[high]:
            low = mid + 1
        elif arr[mid] < arr[high]:
            high = mid - 1
    return None

res = find_max(arr, 0, len(arr) - 1)
print(res)
user_185765970
Related