Given a sorted array of distinct integers shiftArr that is shifted to the left by an unknown offset, we are to implement a function shiftedArrSearch that finds and returns the index of a given integer num in shiftArr. If num is not in shiftArr, the function should return -1.

For instance, the sequence [1, 2, 3, 4, 5] becomes [3, 4, 5, 1, 2] after shifting it twice to the left.

In this article, we will discuss how to solve this problem using a modified binary search algorithm. We will also analyze the time and space complexities of the algorithm.

Approach

The idea is to find the index of the smallest element in the array, which is the index where the array is rotated. Once we find this index, we can divide the array into two parts and perform a binary search on the appropriate part to find the target element.

Here are the steps to implement this approach:

1. Find the index of the smallest element in the array using binary search. This can be done by comparing the middle element with the first and last elements of the array. If the middle element is smaller than the last element, we know that the smallest element is in the first half of the array. If it is greater, we know that the smallest element is in the second half of the array. We can repeat this process until we find the smallest element.

2. Once we have the index of the smallest element, we can determine which part of the array to search for the target element. If the target element is greater than the last element of the array, we search the first half of the array. Otherwise, we search the second half of the array.

3. Perform a binary search on the appropriate part of the array to find the target element.

Implementation

Here is the Python implementation of the above approach:

def shiftedArrSearch(shiftArr, num):
    n = len(shiftArr)
    l, r = 0, n-1

    # Find the index of the smallest element in the array
    while l < r:
        mid = (l + r) // 2
        if shiftArr[mid] > shiftArr[r]:
            l = mid + 1
        else:
            r = mid

    # Determine which part of the array to search for the target element
    if num > shiftArr[n-1]:
        l, r = 0, l-1
    else:
        l, r = l, n-1

    # Perform binary search on the appropriate part of the array
    while l <= r:
        mid = (l + r) // 2
        if shiftArr[mid] == num:
            return mid
        elif shiftArr[mid] < num:
            l = mid + 1
        else:
            r = mid - 1

    # Target element not found
    return -1

In the above code, we first find the index of the smallest element in the array using binary search. We then determine which part of the array to search for the target element. Finally, we perform binary search on the appropriate part of the array to find the target element.

Complexity Analysis

Let n be the length of the input array shiftArr.

Time Complexity

The time complexity of the algorithm is O(log n) because we perform binary search twice on an array of size n.

Space Complexity

The space complexity of the algorithm is O(1) because we only use a few constant-sized variables.

Conclusion

In this article, we discussed how to solve the problem of finding the index of a given integer in a shifted sorted array using a modified binary search algorithm. We first found the index of the smallest element in the array, which is the index where the array is rotated. We then determined which part of the array to search for the target element and performed binary search on the appropriate part of the array to find the target element.

The time complexity of the algorithm is O(log n) and the space complexity is O(1). This makes the algorithm efficient and suitable for large input arrays.

Overall, the approach we discussed in this article is a useful technique for solving similar problems involving rotated or shifted arrays. By understanding this approach, you will be better equipped to solve similar problems in the future.