Tìm kiếm trong Mảng được sắp xếp xoay vòng bằng Python

Hãy xem xét chúng ta có một mảng được sắp xếp theo thứ tự tăng dần và mảng đó được xoay ở một số trục mà bạn chưa 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 tôi đã đưa ra một giá trị mục tiêu cho tìm kiếm. Nếu chúng ta có thể lấy nó trong mảng, thì hãy trả về chỉ mục của nó, nếu không thì trả về -1. Chúng tôi có thể giả định rằng không có bản sao tồn tại trong mảng. Vì vậy, nếu mảng giống như [4,5,6,7,0,1,2], thì đầu ra sẽ là 4. vì chỉ số của phần tử này có mặt ở chỉ số 4.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• low:=0 và high:=độ dài của mảng
• trong khi thấp
• tìm giữa là giữa:=low + (cao - thấp) / 2
• if arr [mid] =target, sau đó trả về mid
• if arr [low] <=arr [mid]
  • nếu target> =arr [low] và target
• nếu không thì
  • nếu target <=arr [high - 1] và target> arr [mid] thì low:=mid + 1, ngược lại high:=mid

Ví dụ (Python)

Hãy cùng chúng tôi xem cách 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