Döndürülmüş sıralı dizide arama

Problem

Artan sırada sıralanmış ve değerleri birbirinden farklı bir dizi, bilinmeyen bir noktadan döndürülmüş: dizinin baş kısmı kesilip sona eklenmiş (hiç döndürülmemiş de olabilir). Bu dizide bir hedef değerin index'ini bul; yoksa -1 döndür. Çözüm O(log n) zamanda çalışmalı.

Girdi:  nums = [15, 18, 22, 3, 6, 9, 11], target = 6
Çıktı:  4

Girdi:  nums = [15, 18, 22, 3, 6, 9, 11], target = 10
Çıktı:  -1

Netleştirme soruları

• Değerler gerçekten farklı mı? (Tekrar varsa en kötü durum O(n)'e çıkar; LeetCode 81.)
• Dizi hiç döndürülmemiş olabilir mi? (Evet; çözüm bu durumda da çalışmalı.)
• Boş dizi gelebilir mi?
• Hedef birden çok kez geçemez (değerler farklı), ama tekrar olsaydı hangi index istenirdi?
• O(log n) şartı kesin mi?

İpuçları

Yaklaşım

Brute force: Lineer arama, O(n). Doğru ama O(log n) şartını karşılamaz; mülakatta söylemek yeterli.

İki aşamalı çözüm: Önce binary search ile dönme noktasını (en küçük elemanın index'ini) bul, sonra hedefin hangi parçada olduğuna karar verip o parçada normal binary search yap. O(log n); iki ayrı binary search yazmak gerektiği için hata yüzeyi daha geniş ama mantığı çok net. Mülakatta tamamen kabul edilir.

Tek geçişli binary search: Her mid için iki yarıdan biri kesinlikle sıralıdır, çünkü dönme noktası (tek "kırılma") en fazla bir yarıda olabilir.

• nums[lo] <= nums[mid]: sol yarı [lo, mid] sıralı. Hedef nums[lo] <= target < nums[mid] aralığındaysa hi = mid - 1, değilse lo = mid + 1.
• Aksi halde sağ yarı [mid, hi] sıralı. Hedef nums[mid] < target <= nums[hi] aralığındaysa lo = mid + 1, değilse hi = mid - 1.

<= karşılaştırması lo == mid durumu için kritik: iki elemanlı [3, 1] dizisinde mid = lo olur ve sol "yarı" tek elemandır; tek eleman tanım gereği sıralıdır. < yazarsan bu durumda yanlış yarıya gidersin.

Aralık kontrollerinde hangi ucun dahil olduğu da önemli: nums[mid] == target zaten kontrol edildiği için mid aralığa dahil edilmez (target < nums[mid]), ama lo ve hi dahildir.

Java çözümü

public final class SearchInRotatedSortedArray {

    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;                          // kapalı aralık [lo, hi]
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[lo] <= nums[mid]) {                           // sol yarı [lo, mid] sıralı
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {                                               // sağ yarı [mid, hi] sıralı
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

mid = lo + (hi - lo) / 2 yazımı (lo + hi) / 2'nin büyük dizilerde int taşmasını önler; Java'nın kendi Arrays.binarySearch'ü bunun yerine (lo + hi) >>> 1 kullanır.

Karmaşıklık

• Zaman: O(log n); her iterasyonda arama aralığı yarıya iner.
• Bellek: O(1).
• Değerler tekrar edebilseydi nums[lo] == nums[mid] == nums[hi] durumunda hangi yarının sıralı olduğu bilinemez; lo++ ile tek adım ilerlenir ve en kötü durum O(n) olur.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; ayrıca 5.000 rastgele girdide (1-20 farklı değer, rastgele dönme noktası, dizide olan ve olmayan hedefler) lineer arama ile karşılaştırıldı.

Mülakatçı için

Binary search sorularında asıl sınav sınır disiplinidir: kapalı mı yarı açık mı aralık, < mı <= mı, mid ± 1 mi. Bu soruda ek olarak adayın "bir yarı her zaman sıralı" değişmezini bulup bulamadığı ölçülür. Çözümü ezberden yazan aday çoğu zaman iki elemanlı dizide takılır; [3, 1] ile 1'i aramasını istemek iyi bir kontroldür.

İpucu zamanlaması: Aday lineer aramadan sonra ilerleyemezse "ortadan böldüğünde iki yarı hakkında ne söyleyebilirsin?" diye sor. İki aşamalı (önce pivot) çözüm önerirse kabul et; isterse tek geçişe geçebileceğini söyle. Kod bittikten sonra mutlaka küçük dizilerle (1 ve 2 eleman) dry run iste.

Takip soruları:

1. Değerler tekrar edebilseydi? (Beklenen: nums[lo] == nums[mid] iken lo++; en kötü O(n); LeetCode 81.)
2. Dizinin kaç kez döndürüldüğünü (en küçük elemanın index'ini) bul. (Beklenen: nums[mid] > nums[hi] ise lo = mid + 1, değilse hi = mid; LeetCode 153.)
3. Bu dizi, gün içinde saat 00:00'dan değil 09:00'dan başlayan bir zaman serisi gibi düşünülebilir. Gerçek hayatta döndürülmüş sıralı veriyi nerede görürsün? (Beklenen: ring buffer / circular log; başlangıç offset'i bilinirse index dönüşümüyle normal binary search.)

Benzer problemler

• Find Minimum in Rotated Sorted Array (LeetCode 153).
• Search in Rotated Sorted Array II (LeetCode 81): tekrarlı değerler.
• Find Peak Element (LeetCode 162): sıralı olmayan dizide binary search.
• Koko Eating Bananas (LeetCode 875): cevap üzerinde binary search (bu sette: koko-eating-bananas).