JavaScript'te İkili Arama

İkili arama, sıralanmış bir listedeki belirli bir öğenin konumunu bulmak için kullanılan bir arama algoritmasıdır. İstenen eleman bulunana veya elemanın listede olmadığı belirlenene kadar listeyi tekrar tekrar ikiye bölerek çalışır.

İkili arama nasıl çalışır?

İkili aramanın nasıl çalıştığını anlamak için bir örneği ele alalım. Sıralanmış bir tamsayı listemiz olduğunu ve 37 sayısının konumunu bulmak istediğimizi varsayalım. İkili arama algoritması şu şekilde çalışır:

1. Öncelikle listenin ortadaki elemanını belirliyoruz. Ortadaki eleman 37 ise işimiz biter ve elemanın pozisyonunu döndürürüz.
2. Ortadaki eleman 37 değilse 37'den büyük mü küçük mü diye bakıyoruz. 37'den büyükse istenen elemanın listenin sol yarısında olması gerektiğini biliyoruz. 37'den küçükse, istenen öğenin listenin sağ yarısında olması gerektiğini biliyoruz.
3. Listenin uygun yarısında eleman bulunana veya elemanın listede olmadığı belirlenene kadar işlemi tekrarlıyoruz.

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

Neden ikili arama kullanmalıyız?

Peki, neden ikili arama kullanmalıyız? İkili aramanın ana avantajlarından biri zaman karmaşıklığıdır. En kötü senaryoda, ikili aramanın zaman karmaşıklığı O(log n)'dir, bu da büyük listeler için doğrusal aramadan (O(n)) çok daha hızlı olduğu anlamına gelir. Bu, onu büyük veri kümelerini aramak için verimli bir algoritma yapar.

Sonuç olarak, ikili arama, sıralanmış bir listedeki belirli bir öğenin konumunu hızlı bir şekilde bulmak için kullanışlı bir algoritmadır. Zaman karmaşıklığı, onu büyük veri kümelerini aramak için uygun hale getirir ve JavaScript'te uygulanması nispeten kolaydır.