ค้นหาในอาร์เรย์หมุนซ้ำ (Search in Rotated Sorted Array II) ใน Python

โจทย์: อาร์เรย์เรียงเพิ่มแต่หมุนที่จุดไม่ทราบ (อาจมีค่าซ้ำ) ค้นหา target คืน True/False

ตัวอย่าง

nums = [2,5,6,0,0,1,2], target = 0
Output: True

อัลกอริทึม: Modified Binary Search

จัดการ duplicate ด้วยการ skip low/high เมื่อ nums[low] == nums[mid] == nums[high]

ตัวอย่างโค้ด Python

class Solution(object):
    def search(self, nums, target):
        low, high = 0, len(nums) - 1
        
        while low <= high:
            mid = (low + high) // 2
            
            if nums[mid] == target:
                return True
            
            # จัดการ duplicate: ไม่รู้ด้านไหน sorted ต้อง skip
            if nums[low] == nums[mid] == nums[high]:
                low += 1
                high -= 1
                continue
            
            # ด้านซ้าย sorted
            if nums[low] <= nums[mid]:
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            # ด้านขวา sorted
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1
        
        return False

# ทดสอบ
ob = Solution()
print(ob.search([2,5,6,0,0,1,2], 0))  # Output: True

ตัวอย่าง Input/Output

Input: [2,5,6,0,0,1,2] 0
Output: True

หมายเหตุ: กรณี worst-case (ทุกตัวเหมือนกัน) Time O(n), แต่วงส่วนใหญ่ O(log n)