Tìm kiếm trong mảng xoay đã sắp xếp trong Python

Xét một mảng được sắp xếp tăng dần, và mảng đó bị xoay tại một điểm pivot không biết trước. Ví dụ, [0,1,2,4,5,6,7] có thể trở thành [4,5,6,7,0,1,2]. Chúng ta được cho một giá trị mục tiêu để tìm kiếm. Nếu tìm thấy trong mảng, trả về chỉ số của nó, ngược lại trả về -1. Giả sử không có phần tử trùng lặp trong mảng. Ví dụ, nếu mảng là [4,5,6,7,0,1,2], mục tiêu 0, đầu ra sẽ là 4 (chỉ số của 0).

Để giải quyết, chúng ta làm theo các bước sau:

• low := 0 và high := độ dài mảng.
• Khi low < high:
  • Tìm mid như mid := low + (high - low)//2.
  • Nếu arr[mid] == target, trả về mid.
  • Nếu arr[low] <= arr[mid]:
    • Nếu target >= arr[low] và target < arr[mid], thì high := mid, ngược lại low := mid + 1.
  • Ngược lại:
    • Nếu target <= arr[high - 1] và target > arr[mid], thì low := mid + 1, ngược lại high := mid.
• Trả về -1.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def search(self, nums, target):
        low = 0
        high = len(nums)
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            if nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid
                else:
                    low = mid + 1
            else:
                if target <= nums[high - 1] and target > nums[mid]:
                    low = mid + 1
                else:
                    high = mid
        return -1

ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))

Đầu vào

[4,5,6,7,0,1,2] 0

Đầu ra

5