A short summary of 3 algorithms for implementing rotated arrays in Python3

I. Introduction

Rotated arrays are a common data structure problem, usually an ordered array that is rotated so that all elements are in reverse order. For example, given an array [4,5,6,7,0,1,2], it may be rotated to [0,1,2,4,5,6,7]. Solving the problem of rotating arrays is important for understanding algorithm design and data structures.

II. Linear time complexity algorithms

The basic idea of the linear time complexity algorithm is to use the idea of binary search to find the target element by continuously narrowing the search range. The specific steps are as follows:

Determines the left and right boundaries of the array;
Determine the subarray in which the target element is located by binary lookup;
If the target element is in the left half, return the index directly;
If the target element is in the right half, the relative position is calculated and returned.
Here is the Python3 code implementation:

def search_rotate_array(nums, target):  
    left, right = 0, len(nums) - 1  
    while left <= right:  
        mid = (left + right) // 2  
        if nums[mid] == target:  
            return mid  
        if nums[left] <= nums[mid]:  
            if target >= nums[left] and target < nums[mid]:  
                right = mid - 1  
            else:  
                left = mid + 1  
        else:  
            if target > nums[mid] and target <= nums[right]:  
                left = mid + 1  
            else:  
                right = mid - 1  
    return -1

III. Dichotomous Lookup Algorithm

The bisection finding algorithm is a common search algorithm for ordered arrays. For rotated arrays, we can also utilize the idea of bisection finding, but we need to make some adjustments to the search process. The specific steps are as follows:

Determines the left and right boundaries of the array;
Determine the subarray in which the target element is located by binary lookup;
Determines the position of the target element and returns it based on the size of the subarray and the positional relationship between the left and right boundaries.
Here is the Python3 code implementation:

def search_rotate_array_binary(nums, target):  
    left, right = 0, len(nums) - 1  
    while left <= right:  
        mid = (left + right) // 2  
        if nums[mid] == target:  
            return mid  
        if nums[left] <= nums[mid]:  
            if target >= nums[left] and target < nums[mid]:  
                right = mid - 1  
            else:  
                left = mid + 1  
        else:  
            if target > nums[mid] and target <= nums[right]:  
                left = mid + 1  
            else:  
                right = mid - 1  
    return -1

IV. Partitioning algorithms

A partition algorithm is an algorithm that decomposes a problem into a number of subproblems and then recursively solves the subproblems. For rotating arrays, we can discuss them in three cases:

The point of rotation is in the left half;
The point of rotation is in the right half;
The rotation point is in the center.
In each case, we process the subarrays of the left half, the middle half, and the right half, and then merge the results to find the location of the target element and return it.

Here is the Python3 code implementation:

def search_rotate_array_divide(nums, target):  
    def find_pivot(nums):  
        if nums[0] <= nums[-1]:  
            return 0  
        for i in range(len(nums) // 2):  
            if nums[i] > nums[i + len(nums) // 2]:  
                return i + 1  
        return -1  
      
    pivot = find_pivot(nums)  
    if pivot == -1:  
        return binary_search(nums, 0, len(nums) - 1, target)  
    if pivot == 0:  
        if nums[0] <= target:  
            return binary_search(nums, 0, pivot - 1, target)  
        else:  
            return binary_search(nums, pivot, len(nums) - 1, target)  
    if nums[pivot - 1] <= target and nums[pivot] >= target:  
        return pivot - 1  
    if nums[pivot] <= target and nums[pivot + 1] >= target:  
        return pivot  
    if nums[0] <= target:  
        return binary_search(nums, 0, pivot - 1, target)  
    else:  
        return binary_search(nums, pivot, len(nums) - 1, target)

V. Performance analysis

Linear Time Complexity Algorithm: the time complexity of this algorithm is O(log n), where n is the length of the array. The algorithm performs well when dealing with large rotated arrays.
Dichotomous Finding Algorithm: the time complexity of this algorithm is also O(log n). Compared to the linear time complexity algorithm, the bisection lookup algorithm is simpler to implement, but it requires predetermining the location of the rotation point.
PARTITIONING ALGORITHM: The time complexity of this algorithm is O(log n), but the implementation is more complex. When dealing with large rotated arrays, the partition algorithm performs well, but care needs to be taken to deal with various special cases.

VI. Conclusion

The rotated array problem is a common data structure problem that is important for understanding algorithm design and data structures. This paper presents three algorithms for implementing rotated arrays: the linear time complexity algorithm, the bisection lookup algorithm, and the partition algorithm.

In practice, the appropriate algorithm can be chosen according to the specific situation. Linear time complexity algorithm and bisection finding algorithm are simple to implement and suitable for small and medium-sized rotating arrays; while the partition algorithm is more complex to implement, but suitable for large rotating arrays. By reasonably selecting and optimizing the algorithms, the performance and stability of the program can be improved.

To this point, this article on Python3 to achieve a rotated array of three algorithms summary of the article is introduced to this, more related Python3 rotated array content, please search for my previous posts or continue to browse the following related articles I hope you will support me in the future more!