Sıralanmış Dizide İki İşaretçi

İki işaretçi tekniği, bir diziyi iç içe döngüler yerine iki indeksle tarar; böylece birçok O(n^2) fikrini tek ve temiz bir O(n) geçişine dönüştürür. 🎯

Klasik sürüm sıralanmış bir dizi gerektirir. Sıra kurmanızı sağlar: sağa ilerlemek değeri büyütür, sola ilerlemek küçültür; böylece her adım gerçek bir karara dönüşür.

Bir işaretçiyi sol uca, diğerini sağ uca yerleştirerek başlayın. Birbirlerine bakarlar ve aralarındaki mesafeyi yavaşça kapatırlar.

Her adımda tam olarak bir işaretçiyi içeri doğru ilerletirsiniz. Dizinin sırası, hedefinize yaklaşmak için hangi tarafı ilerletmeniz gerektiğini söyler.

left < right olduğu sürece döngüyü sürdürün. Birbirlerine ulaştıklarında veya birbirlerini geçtiklerinde, işe yarayan her çift kontrol edilmiş olur ve durabilirsiniz.

a[left] + a[right] ifadesini geçerli adayınız olarak değerlendirin. Bunu hedefle karşılaştırmak, sırada daha büyük mü yoksa daha küçük mü bir değere ihtiyaç duyduğunuzu gösterir.

Toplam hedeften küçükse, daha fazlasına ihtiyacınız vardır. Dizi artan sırada olduğundan, sol işaretçiyi daha büyük değerlere doğru sağa ilerletin.

Toplam hedeften büyükse, daha azına ihtiyacınız vardır. Toplamı azaltmak için sağ işaretçiyi daha küçük değerlere doğru sola ilerletin.

Her hareket, hiç denemeniz gerekmeyen bir çift grubunu tamamen eler. Bu nedenle tarama karesel değil, doğrusaldır.

Yalnızca eşleşemeyecek çiftleri elersiniz; bu nedenle doğru yanıtı asla atlamazsınız. İki işaretçiyi yarışmalarda güvenilir kılan da bu güvencedir.

Aynı fikir şu varyantlara da güç verir: yerinde tersine çevirme, bölümlere ayırma ve birleştirme. Buluşan işaretçiler fikrini kavradığınızda bunların hepsi tanıdık gelir.

Hedef toplamı bulmak için sıralanmış bir diziyi iki uçtan tarıyorsunuz.

İki işaretçi, sıralanmış bir diziyi iki uçtan tarar ve her adımda birini içeri ilerletir; koşul left < right olduğu sürece devam eder. Doğrusal, doğru ve birçok yöntemin temelidir. 🚀