6-10PM challenge problem #006

Shifted Array Search

A sorted array of distinct integers shiftArr is shifted to the left by an unknown offset and you don’t have a pre-shifted copy of it. For instance, the sequence 1, 2, 3, 4, 5 becomes 3, 4, 5, 1, 2, after shifting it twice to the left.

Given shiftArr and an integer num, implement a function shiftedArrSearch that finds and returns the index of num in shiftArr. If num isn’t in shiftArr, return -1. Assume that the offset can be any value between 0 and arr.length - 1.

Explain your solution and analyze its time and space complexities.

Example

input:  shiftArr = [9, 12, 17, 2, 4, 5], num = 2 # shiftArr is the
                                                 # outcome of shifting
                                                 # [2, 4, 5, 9, 12, 17]
                                                 # three times to the left

output: 3 # since it’s the index of 2 in arr


 

Solution

Comments

[Vidit Sarkar]

Here is a Python solution,

def shiftArr(arr , num):
    low, high = 0, len(arr)-1

    while(low <= high):
        mid = (low + high)//2
        if(arr[mid] == num):
            return mid

        if(arr[low] < arr[mid]):
            if(num >= arr[low] and num < arr[mid]):
                high = mid - 1
            else:
                low = mid + 1
        else:
            if(num > arr[mid] and num <= arr[high]):
                low = mid + 1
            else:
                high = mid - 1

    return -1

Test cases,

print(shiftArr([9, 12, 17, 2, 4, 5], 2)) # output -> 3
print(shiftArr([9, 12, 17, 2, 4, 5], 3)) # output -> -1
print(shiftArr([9, 12, 17, 2, 4, 5], 17)) # output -> 2
print(shiftArr([1],1)) # output -> 0
print(shiftArr([1],2)) # output -> -1
print(shiftArr([],3)) # output -> -1

[akbhairwal]

if(num >= arr[low] and num < arr[mid]):

In equal case, you should return 'low' , there is no need to do anything.