Divide and conquer nümunəsi

[codex]

Böl və idarə et (Divide and Conquer) nümunəsi, verilənləri kiçik hissələrə bölməklə və sonra hər bir hissədə təkrarlanan proses tətbiq etməklə problemləri həll etməyə əsaslanır. Bu yanaşma, xüsusilə axtarış və sıralama alqoritmlərində geniş istifadə olunur.

---

Məsələ

Verilmiş sıralanmış tam ədəd massivində, müəyyən bir dəyəri tapan bir funksiya yazın. Əgər dəyər varsa, onun indeksini qaytarsın, əks halda -1 qaytarsın.

---

Naiv həll (O(n))

Bu yanaşma, massivin hər bir elementini yoxlayır və uyğunluğu tapana qədər davam edir.

Kod:

function search(array, num) {
  for (let i = 0; i < array.length; i++) {
    if (num === array[i]) return i;
  }

  return -1;
}

console.log(search([1, 2, 3, 4, 5, 6, 7, 8], 5)); // 4

Mürəkkəblik: O(n) (çünki ən pis halda bütün elementləri yoxlamalıyıq).

---

Böl və idarə et həlli (O(log n))

Bu yanaşma massivi iki hissəyə bölərək daha sürətli həll təklif edir (İkili Axtarış – Binary Search).

Kod:

function search(array, num) {
  let min = 0;
  let max = array.length - 1;

  while (min <= max) {
    let middle = Math.floor((min + max) / 2);
    let currentElement = array[middle];

    if (currentElement < num) {
      min = middle + 1;
    } else if (currentElement > num) {
      max = middle - 1;
    } else {
      return middle;
    }
  }

  return -1;
}

console.log(search([1, 2, 3, 4, 5, 6, 7, 8], 5)); // 4

Mürəkkəblik: O(log n) (çünki hər iterasiyada massivi yarıya bölürük).

---

Nəticə

Naiv olan həll tək-tək axtarır və O(n) vaxt aparır.
Böl və idarə et həlli kəsərək daha sürətli nəticə verir və O(log n) mürəkkəbliyinə malikdir.

İkili axtarış metodu böyük verilənlər üzərində daha effektiv işləyir!