জাভাস্ক্রিপ্টে সর্টেড অ্যারেতে নম্বর ইনসার্ট করা (বাইনারি সার্চ দিয়ে)

সমস্যা বিবরণ

একটি সর্টেড নাম্বার অ্যারে এবং একটি নম্বর দেওয়া আছে। নতুন নম্বরটি সর্ট অর্ডার রক্ষা করে অ্যারেতে ইনসার্ট করতে হবে। নতুন অ্যারে তৈরি করা যাবে না (in-place)।

সমাধান

const arr = [6, 7, 8, 9, 12, 14, 16, 17, 19, 20, 22];
const num = 15;

const findIndex = (arr, val) => {
  let low = 0, high = arr.length;
  while (low < high) {
    let mid = (low + high) >>> 1;
    if (arr[mid] < val) low = mid + 1;
    else high = mid;
  }
  return low;
};

const insertAt = (arr = [], num) => {
  const position = findIndex(arr, num);
  for (let i = position; typeof arr[i] !== 'undefined'; i++) {
    // স্ব্যাপিং থার্ড ভেরিয়েবল ছাড়া
    num += arr[i];
    arr[i] = num - arr[i];
    num -= arr[i];
  }
  arr.push(num);
};

insertAt(arr, num);
console.log(arr);

আউটপুট

[ 6, 7, 8, 9, 12, 14, 15, 16, 17, 19, 20, 22 ]

ব্যাখ্যা

• findIndex: বাইনারি সার্চ দিয়ে ইনসারশন পজিশন O(log n) এ বের করা।
• insertAt: পজিশন থেকে শুরু করে এলিমেন্টগুলো এক পেছনে ধাক্কা দেওয়া (সোয়াপ ট্রিক দিয়ে) এবং শেষে নতুন নম্বর পুশ করা।
• সোয়াপ ট্রিক: a += b; b = a - b; a -= b;