ค้นหาใน Rotated Sorted Array ใน Python

ลองพิจารณาว่าเรามีอาร์เรย์ที่จัดเรียงจากน้อยไปหามาก และจะหมุนไปที่จุดหมุนที่คุณไม่รู้จักล่วงหน้า ตัวอย่างเช่น [0,1,2,4,5,6,7] อาจกลายเป็น [4,5,6,7,0,1,2] เราได้ให้ค่าเป้าหมายในการค้นหา หากเราได้รับในอาร์เรย์ ให้ส่งคืนดัชนี มิฉะนั้นให้คืนค่า -1 เราสามารถสันนิษฐานได้ว่าไม่มีข้อมูลซ้ำกันในอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นแบบ [4,5,6,7,0,1,2] ผลลัพธ์จะเป็น 4 เนื่องจากดัชนีขององค์ประกอบนี้มีอยู่ที่ดัชนี 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ต่ำ :=0 และสูง :=ความยาวของอาร์เรย์
• ในขณะที่ต่ำ <สูง
  • หา mid เป็น mid :=ต่ำ + (สูง - ต่ำ)/2
  • ถ้า arr[mid] =เป้าหมาย ให้คืนค่า mid
  • ถ้า arr[ต่ำ] <=arr[mid]
    • ถ้าเป้าหมาย>=arr[ต่ำ] และเป้าหมาย
  • อย่างอื่น
    • ถ้าเป้าหมาย <=arr[สูง - 1] และเป้าหมาย> arr[mid] แล้วต่ำ :=กลาง + 1 มิฉะนั้นสูง :=กลาง
• คืน -1

ตัวอย่าง(Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −

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))

อินพุต

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

ผลลัพธ์

5