Döndürülmüş sıralı bir dizide (Search in Rotated Sorted Array) bir hedefi O(log n) zamanda arayın.

[4,5,6,7,0,1,2] gibi bir dizide her mid noktasında iki yarıdan biri mutlaka sıralıdır. Hangi yarının sıralı olduğunu bulup hedefin o aralıkta olup olmadığına göre aramayı daraltırız; bu, binary search'ün değiştirilmiş hâlidir.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:            # sol yarı sıralı
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                # sağ yarı sıralı
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

print(search([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))  # -1

Kilit noktalar

• nums[lo] <= nums[mid] karşılaştırmasındaki =, lo == mid olduğu iki elemanlı durumlar için gereklidir.
• Hedef aralık kontrolünde bir uç kapalı, diğer uç açık olmalıdır; mid zaten kontrol edildi.

Karmaşıklık

O(log n) zaman, O(1) bellek.

İlgili sorular

• Find Minimum in Rotated Sorted Array: nums[mid] > nums[hi] ise minimum sağdadır (lo = mid + 1), değilse hi = mid.
• Tekrarlayan elemanlar varsa: nums[lo] == nums[mid] == nums[hi] durumunda hangi yarının sıralı olduğu anlaşılamaz; lo += 1, hi -= 1 yapılır ve en kötü durum O(n) olur.