Search in Rotated Sorted Array ใน Python - ค้นหาในอาร์เรย์หมุน

พิจารณาอาร์เรย์ที่เรียงจากน้อยไปมาก แล้วหมุน (rotated) ที่จุด pivot ไหนที่ไม่ทราบล่วงหน้า ตัวอย่าง [0,1,2,4,5,6,7] อาจกลายเป็น [4,5,6,7,0,1,2] ให้ค่า target ต้องค้นหา ถ้าพบคืน index มิฉะนั้นคืน -1 สมมติไม่มี duplicate ตัวอย่าง [4,5,6,7,0,1,2] target 0 ผลลัพธ์ index 4

ขั้นตอนการทำงาน (Modified Binary Search)

1. low := 0, high := len(array)
2. วนลูป while low < high:
   • mid := low + (high - low) // 2
   • ถ้า arr[mid] == target คืน mid
   • ถ้า arr[low] <= arr[mid] (ซ้ายเรียงแล้ว):
     • ถ้า target >= arr[low] and target < arr[mid]: high := mid มิฉะนั้น low := mid + 1
   • มิฉะนั้น (ขวาเรียงแล้ว):
     • ถ้า target <= arr[high-1] and target > arr[mid]: low := mid + 1 มิฉะนั้น high := mid
3. คืน -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