I learn c++

Binary Search Pt.2

Şimdi biz binary search-in hazır versiyonunu öğreniceğiz. Bu hazır versiyon bize ona verdiğimiz massivde verdiğimiz rakamın olup olmadığını true ve ya false ile söylüyor. Bu çok kullanılmasa da bazen kodunuzu yazmaya harcadığınız süreyi ciddi şekilde azaltıyor.

Yazılışı bu şekilde.

Şimdi ise bu bölüm kısmına gelelim. Upper Bound ve Lower Bound. Bunlar biraz garip gelebilir ama hemen ne işe yaradıklarını söyleyeyim. Öncelikle bunların binary search de olmasının sebebi işlerini binary search taktiğiyle görüyorlar. Peki ya ne işe yarıyorlar. Öncelikle Lower Bound-dan başlayalım.

Lower Bound

Lower boundun yazılışı şu şekilde:

Aslında bu kodunda biz garip harfler ve rakamlar görüyoruz. Bunun sebebi lower boundun değeri değil onun adresini yollaması. Bunu henüz anlayamaya bilirsiniz. Aslında çok küçük bir kısmını Array bölümünde söylemiştim ama Adresleri öğrendiğimiz de bunu daha iyi anlayacaksınız. Peki ya bu kodun kaytardığı adresteki değer ne? Bu değer şöyle götürülüyor.

1) Öncelikle eğer k massivde yoksa k-dan büyük ilk elementin adresini veriyor.
2) Eğer k massivde varsa va sadece 1 taneyse k-ın adresini veriyor.
3) Eğer k massivde varsa ve 2 veya daha fazlaysa bu zaman ilk k-ın adresini veriyor.

Dikkat: Değerler aynı olsada adresler her zaman farklıdır.

Şimdi bize hiç bir problemde adres sorulmayacağı için bunu nasıl index-e çevireceğimizi öğrenelim. Bu aslında çok kolay. Bunun için cevabımızdan massivin ilk elemetinin adresini çıkarmamız gerekiyor. Böylelikle değerimizin massivdeki indexini almış olacağız.

Hatırlatma: İlk değerin adresi array-de array-in ismi yani a, vector-de ise v.begin()

Upper Bound

Upper boundun yazılışı lower bound ile aynı sadece lower_bound yerine upper_bound yazıyoruz ve ilk iteratoru çıkarıyoruz.

Peki bu bize neyi veriyor?

1) Eğer k massivde yoksa k-dan büyük ilk elementin adresini
2) Eğer k massivde varsa ve sadece bir taneyse k dan büyük ilk elementin adresini
3) Eğer k massivde varsa ve 2 veya daha fazlaysa k dan büyük ilk elementin adresini
4) Eğer k dan büyük ilk elementden bir taneyse onun adresini
5) Eğer k dan büyük ilk elementden 2 veya daha fazlaysa ilk-in in adresini

Şimdi ise bir probleme bakalım:

Problem:
Ayşe mağazaya garip bir şey fark etti. Meyvelerin fiyatlarına göre azalamayan şekilde sıralandığını gördü. Tezgahta n farklı meyve vardı. Ayşenin aklına bir soru geldi. Bu meyveler arasında kaç tane farklı meyve türünün fiyatı k-a eşit?
Giriş:
İlk satırda n rakamı.
İkinci satırda n rakam var. Meyvelerin fiyatları.
Son satırda k rakamı.
Çıkış:
Bir rakam. Fiyatı k-a eşit olan meyvelerin sayı.

Bu problem aslında çok meşhur ve kolay bir problem. Bunu yazmak için sadece upper bound-dan lower bound-u çıkarmanız gerekiyor. İsterseniz önce her birinden ilk elementin adresini çıkarıp sonrasında indexleri bir birinden çıkarada bilirsiniz. Her iki yol doğru ama çoğu zaman ilk yol yazılıyor.

Kod: