binary search

• ikiye kesme yöntemiyle aynı mantıkla çalışır.
  (bkz: ikiye kesme yöntemi)
• while(sol<=sag)
  { orta=(sol+sag)/2;
  if(aranan= =a[orta])
  return orta;
  else if (aranan>a[orta])
  sol=orta+1;
  else
  sag=orta-1;}
  seklinde basit algoritma.yukari asagi diye bi oyun vardi.sayi tahmin etmece,onda kullanilirdi bu.aslinda direk bu yontemi kullanmayi orda kendi kendine kesfedersin.
• linear search'e göre performansı gayet yüksektir. cok karizmatiktir. 1024 elemanlı bir dizide en boktan durumda bile maximum 10 kar$ıla$tırmada işi bitirir.
• literaturde hatasiz bir surumunu yazmak yakla$ik 40 yil surmu$.
  
  (bkz: integer overflow)
• ssg'nin dedigi sorun c/c++/java gibi dillerde yazacaksaniz ortaya cikar cunku bu dillerde integerlar sayi degil mod 2^3`dir. python/ruby/lisp gibi dillerde cikmaz boyle bir sorun. ayni sorun mergesort'ta da vardir.
  
  middle item'i bulmak icin java'da mid = (a+b) >>> 1; denilebilir fakat c++ unsigned shift right desteklemediginden middle item'i bulmak icin mid = (a&b)+((a^b) >> 1) denmeli.
  
  konuyla inanilmaz derece alakasiz olsa da java unsigned left'i desteklemez iken c# destekler.
  
  bu kucuk hataya programming pearls kitabinin 46. ve 80. sayfalarinda anlatilan cesitli algorithmlarda rastlayabilirsiniz.
  
  edit: shift left, right'i yanlis yazmisim. unsigned left right ne degil mi?
• http://www.lojik1.com/…inkli-listede-binary-search/
• (bkz: bisection method)
• jon bentley'in cacm'de cikan "writing correct programs" adli bir yazisinda, bu algoritma'da sikca yapilan bug'lari anlattigi bir yazida 20 yildan fazla surece goze carpmamis bir bug kalmistir.
  
  eger mid = (low+high)/2 yapiyorsaniz bunun integer overflow'a dusme sansi epey yuksek, bunun yerine, mid = low + (high – low)/2 yaparsaniz bu sorun ortadan kalkiyor.
  
  buna ek olarak, eger array indexlerinde negatif subscript notasyonu kullanilabiliyorsa, misal arr[-1] son elemani veriyorsa falan, (python misal) "high – low" ifadesinde low negatif buyuk bir sayi oldugunda, high pozitif kaldiginda yine integer overflow'a kucak acarsiniz. o zaman "(low+high)/2" ye donuste suphesiz ki bereket vardir.
• binary searchi sorted arrayde sayı bulmaya indirgemeye gerek yok.
  mesela boolean(true/false) dönen bir f(x) fonksiyonu, eğer belli bir x değerinden büyük iken true dönüyorsa ve o x den küçük iken false dönüyor ise, x i , o(log deger_kumesinin_sizeı) işlemde bulmanıza yarar.
  
  competitive programming ile ilgileniyorsanız bazı sorularda cevaba da binary search atabileceğinizi aklınızdan çıkarmayın işe yarayabiliyor.
  
  cevaba binary search uygulayabileceğiniz örnek soru
• arama algoritması, yapı olarak parçala fethet (bkz: divide and conquer) yaklaşımının bir uygulamasıdır. her adim için ikiye parçalama gerçekleştirilir