JavaScript-এ বাইনারি সার্চ অ্যালগরিদম ইমপ্লিমেন্টেশন

ভূমিকা

বাইনারি সার্চ (Binary Search) একটি দক্ষ সার্চিং অ্যালগরিদম যা **সর্টেড অ্যারে** (সাজানো অ্যারে) তে O(log n) টাইম কমপ্লেক্সিটিতে এলিমেন্ট খুঁজে বের করে। এটি লিনিয়ার সার্চ (O(n)) এর চেয়ে অনেক দ্রুত বড় ডেটাসেটের জন্য।

সম্পূর্ণ কোড (রিকারসিভ)

const arr = [2, 4, 6, 6, 8, 8, 9, 10, 13, 15, 17, 21, 24, 26, 28, 36, 58, 78, 90];

const binarySearch = (arr, start, end, num) => {
  const mid = start + Math.floor((end - start) / 2);
  
  if (start <= end) {
    if (arr[mid] === num) {
      return mid; // পাওয়া গেল
    }
    if (num < arr[mid]) {
      return binarySearch(arr, start, mid - 1, num); // বাম পাশে খুঁজুন
    }
    if (num > arr[mid]) {
      return binarySearch(arr, mid + 1, end, num); // ডান পাশে খুঁজুন
    }
  }
  return -1; // না পাওয়া
};

console.log(binarySearch(arr, 0, arr.length - 1, 13)); // 8 (ইন্ডেক্স)
console.log(binarySearch(arr, 0, arr.length - 1, 11)); // -1 (নেই)

আউটপুট

8
-1

বাইনারি সার্চ কীভাবে কাজ করে

1. মিড পয়েন্ট বের করুন: `mid = start + Math.floor((end - start) / 2)`
2. তুলনা করুন: টার্গেট মিড এলিমেন্টের সাথে তুলনা করুন
3. ন-arrow করুন:
   • টার্গেট < মিড → বাম نصفে খুঁজুন (`end = mid - 1`)
   • টার্গেট > মিড → ডান نصفে খুঁজুন (`start = mid + 1`)
   • টার্গেট == মিড → পাওয়া গেল, ইন্ডেক্স রিটার্ন
4. বেস কেস: `start > end` হলে এলিমেন্ট নেই, -1 রিটার্ন

ইটারেটিভ সংস্করণ (Iterative - প্রস্তাবিত)

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

ইটারেটিভ সংস্করণ কল স্ট্যাক ব্যবহার করে না, তাই বড় অ্যারের জন্য নিরাপদ।

টাইম ও স্পেস কমপ্লেক্সিটি

পূর্বশর্ত (Prerequisites)

• অ্যারে **অবশ্যই সর্টেড** হতে হবে (ascending বা descending)
• ডুপ্লিকেট এলিমেন্ট থাকলে কোনো একটি ইন্ডেক্স রিটার্ন করবে (প্রথম বা শেষ নিশ্চিত নয়)

বিকল্প: প্রথম/শেষ~Occurrence খুঁজে বের করা

// প্রথম occurrence (Lower Bound)
function lowerBound(arr, target) {
  let start = 0, end = arr.length;
  while (start < end) {
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] < target) start = mid + 1;
    else end = mid;
  }
  return start;
}

// শেষ occurrence (Upper Bound - 1)
function upperBound(arr, target) {
  let start = 0, end = arr.length;
  while (start < end) {
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] <= target) start = mid + 1;
    else end = mid;
  }
  return start - 1;
}

বিল্ট-ইন অল্টারনেটিভ

// ES6+: indexOf (লিনিয়ার, O(n))
arr.indexOf(13); // 8

// বাইনারি সার্চ লাইব্রেরি (lodash)
_.sortedIndexOf(arr, 13); // 8

সারাংশ

বাইনারি সার্চ বড় সর্টেড ডেটাসেটে খুব দ্রুত সার্চ করার জন্য অপরিহার্য। রিকারসিভ বানাম ইটারেটিভ - প্রোডাকশনে ইটারেটিভ সংস্করণ প্রস্তাবিত।