Bu gün yeni bir tip öğrenmeyeceğiz. Bir taktik öğreneceğiz. Bunun isminin Binary Search ve bazı problemleri çözerken harcadığımız zamanı ciddi şekilde azaltmak için kullanacağız. Bu yol bize bir massivde her hangi bir rakamın olup olmadığını yoklamak için yardım olacak. Bunu yapmanın 2 yolu var. Birincisi Linear Search ikincisi ise bu gün öğreneceğimiz Binary Search. Linear Search ilk bakışta akla gelen yol yani massivdeki elementlere tek tek bakıp istediğimiz rakamın olup olmadığını yoklamak. Bunun kodunu yazmak istersek şu şekilde olacak:
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
Bu yol çok uzun sürüyor. Onun yerine Binary Search kullansaydık çok daha kısa sürede bunu yapa bilirdik. Dikkat: Eğer bize k-ı massivi almadan önce verseydi massivi alırken her aldığımız rakamı alır almaz k-a eşit olup olmadığını yoklaya biliriz ve bu en kısa yol olurdu.
Bunu yapa bilmek için öncelikle bir massiv alıyoruz ve onu sort yapıyoruz. Sonrasında massivin ortadakı rakamına bakıyoruz. Eğer bizim rakamımız bundan az ise demek ki rakamımız massivin ilk yarısında. Eğer büyükse demek ki ikinci yarısında. Bu zaman biz sadece massivin ilk yarısını veya büyükse ikinci yarısını arıyoruz. Böylelikle önceki kodda harcadığımız zamandan iki kat daha az zaman harcıyoruz. Yani massivimizin ölçüsü n ise biz onun sadece n/2 kısmına bakıyoruz. Şimdi az önce yaptığımız şeyi elimizde olan n/2-lik kısma yapıyoruz ve böylelikle n/4 rakama bakıyoruz. Bunu yaparken massivi böldüğümüz kısma mid(mid = (0 + n-1) /2, 0 ilk indeks n-1 ise son indeks) diyelim. Bu zaman biz bir sonraki adımdaya 0 --> mid-1 yada mid+1 --> n-1 aralığına bakacağız ama biz büyük veya kiçik olduğu hallarına baktık ama eşit olduğu hala bakmadık. Eşit olduğu halde ise demek ki massivde bu rakam var ve biz cevapda YES vereceğiz.
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
Şimdi kodunu yazalım:
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
Tabiki sonda bir problem olmadan olmaz.
Problem: Ahmet yanına n lira alıp oyuncak mağazasına gitti. O buradakı en pahalı oyuncağı almak istiyordu. Tabi ki oyuncağın değeri parasından fazla olamazdı. Ahmete burda ala bileceği en iyi oyuncağın indeksini vermeniz gerekiyor. Giriş: İlk satırda n rakamı. Sonrakı satırda n rakam var Oyuncakların değeri azdan çoka doğru sıralanmış şekilde veriliyor.(Her hangi iki oyuncağın değeri aynı değil). Son satırda k yani Ahmetin parası var. Çıkış: Ahmetin ala bileceği en pahalı oyuncağın indeksi.(Her zaman cevap olduğuna garanti veriliyor)
Bu problemi çözmek için biz az önceki binary search kodunda bazı değişiklikler yapacağız.
Öncelikle eğer a[mid] < k-dan bu bizim cevabımız ola bilir bu yüzden önceden tanımladığımız ans değişenine mid-i eşitliyoruz(indeks istiyor). Bundan sonraysa en pahalısını istediği için aralığımızdaki rakamları artıtmalıyız yani l = mid + 1 yapmalıyız.
Eğer k a[mid]-e eşitse bundan daha büyük cevap olmadığı için cevaba mid-i vere biliriz.
Son şartımızsa a[mid] > k olacak ki bu durumda r = mid - 1 yapacağız ki aralığımız azaltıp daha uygun fiyatlara bakalım.
Böylelikle kodumuz şu şekilde olacak.
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
