在排序和旋转的数组中搜索

1. Overview

In this tutorial, we’ll discuss searching for a number in a sorted and rotated array. We’ll define the problem and provide an example to explain it.

After that, we’ll present an elegant approach to solving it.

2. Defining the Problem

Given an integer, , and a sorted rotated array, , consisting of distinct integers, our task is to find the element’s position whose value equals in . If there’s no such element, we return .

Let’s take a look at the following example:

Assume we want to find the following numbers in the given array:

$\rightarrow$ position = 0
$\rightarrow$ position = -1 (not found)
$\rightarrow$ position = 3

3. Binary Search Approach

3.1. Main Idea

The main idea is to use the binary search technique to find the position of $\boldsymbol{X}$ in $\boldsymbol{A}$ . If we’re currently looking at the value at position middle , we’ll encounter three different cases:

$\boldsymbol{A[middle] = X}$ : meaning that we found our target, and we return its position
$\boldsymbol{A[middle] < X}$ : it means we have to look for a bigger element, so we’ll check whether the leftmost element is greater than , and is less than or equal to the target . In this case, our target should come after the leftmost element. Thus, we might find it in the left part of the array. Otherwise, it should be on the right part.
$\boldsymbol{A[middle] > X}$ : it means we have to look for a smaller element. Therefore, we check whether the rightmost element is less than , and is greater than or equal to . If so, our target should come before the rightmost element. Hence, we can find it in the right part of . Otherwise, it should be on the left part.

In the end, if we finish the binary search and don’t return any value during the search, then our target doesn’t exist in . As a result, we return .

3.2. Algorithm

Let’s take a look at the implementation:

algorithm BinarySearchApproach(A, X):
    // INPUT
    //    A = a sorted and rotated array of distinct integers
    //    X = the integer to find in the array
    // OUTPUT
    //    The position of X in A if found; otherwise -1

    low <- 0
    high <- length(A) - 1

    while low <= high:
        middle <- (low + high) / 2

        if A[middle] = X:
            return middle

        else if A[middle] < X: 
            if A[low] > A[middle] and A[low] <= X:
                high <- middle - 1
            else:
                low <- middle + 1
        else:
            if A[high] < A[middle] and A[high] >= X:
                low <- middle + 1
            else:
                high <- middle - 1

    return -1

The implementation uses the exact ideas described in section 3.1.

The complexity of this algorithm is $\boldsymbol{O(Log_2(N))}$ , where is the length of the given array . The reason behind this complexity is the same as the binary search complexity, where we keep dividing the given array each time into two halves and looking for the target in one of them.

4. Conclusion

This article presented the most efficient way to find an integer in a sorted rotated array. First, we provided an example of the problem. Then we gave an elegant approach to solving it and walked through its implementation.

Persistence

REST

Security