Search in Rotated Sorted Array II - ค้นหาในอาร์เรย์หมุนที่มีค่าซ้ำใน C++

ภาพรวมปัญหา

มีอาร์เรย์จัดเรียงแล้วแต่ถูกหมุนที่ pivot ไม่ทราบ และอาจมีค่าซ้ำ ต้องค้นหา target value คืน true/false

ตัวอย่าง: [2,5,6,0,0,1,2], target=0 → true

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

1. low = 0, high = size of array
2. while low < high:
   • mid = low + (high - low)/2
   • ถ้า nums[mid] == target → return true
   • ถ้า nums[low] == nums[mid] และ nums[high-1] == nums[mid]: low++, high--, continue
   • ถ้า nums[low] <= nums[mid]: (ด้านซ้ายจัดเรียง)
     • ถ้า target >= nums[low] และ target < nums[mid]: high = mid
     • else: low = mid + 1
   • else (ด้านขวาจัดเรียง):
     • ถ้า target <= nums[high-1] และ target > nums[mid]: low = mid + 1
     • else: high = mid
3. return false

ตัวอย่างโค้ด (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 True
            if nums[low] == nums[mid] and nums[high-1] == nums[mid]:
                low += 1
                high -= 1
                continue
            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 False

Input / Output

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