2.4 Bitonic / Rotated Array

Demo: Search in Rotated Sorted Array — LC 33 (Medium — Amazon/Meta/Google High)

Statement (Demo): unique elements বিশিষ্ট একটি sorted array nums কোনো একটি pivot index-এ rotate করা হয়েছে (যেমন: [0,1,2,4,5,6,7] হয়ে গেছে [4,5,6,7,0,1,2])। এই rotated array-তে একটি target মান খুঁজুন। যদি target থাকে তবে তার index return করুন, অন্যথায় -1 return করুন। runtime complexity অবশ্যই O(log n) হতে হবে। উদাহরণ: nums = [4,5,6,7,0,1,2], target = 0 → 4 | ⚡ n ≤ 5000, -10⁴ ≤ nums[i], target ≤ 10⁴

Approach: প্রতি ধাপে দেখুন কোন অর্ধেক sorted (nums[lo] <= nums[mid] হলে বাম)। target সেই sorted অর্ধেকের range-এ পড়লে সেদিকে যান, নাহলে অন্য দিকে।

function search(nums, target) {
  let lo = 0,
    hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      // বাম অর্ধেক sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // ডান অর্ধেক sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Complexity: Time O(log n), Space O(1)