মূল কনটেন্টে যান
🛰️
রিমোট DSA
প্যাটার্ন•টপিক 2 · Binary Search

2.4 Bitonic / Rotated Array

চিনবেন কীভাবে
"rotated sorted array", "peak/mountain element", "bitonic" — the array is not fully sorted, but one half is always sorted; use that half to decide where to go
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

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

Statement (Demo): A sorted array of unique values nums was rotated at some pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Return the index of target, or -1. Must run in O(log n). Example: nums=[4,5,6,7,0,1,2], target=0 → 4 | ⚡ n ≤ 5000, -10⁴ ≤ nums[i], target ≤ 10⁴

Approach: At each step, find which half is sorted (nums[lo] <= nums[mid] means the left half). If the target lies in that sorted half's range, go there; otherwise go to the other half.

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]) {
      // left half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // right half is 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)

Demo · Search in Rotated Sorted Arrayplan · দিন ০৩০LC 33
নোট · ফাঁকা

প্রবলেম

  • Find Minimum in Rotated Sorted Arrayplan · দিন ০০৫LC 153

    Statement: A sorted array of unique values was rotated between 1 and n times. Return its minimum element in O(log n).
    Example: nums=[3,4,5,1,2] → 1 | ⚡ n ≤ 5000, -5000 ≤ nums[i] ≤ 5000

    নোট · ফাঁকা
  • Find Peak Elementplan · দিন ০১৯LC 162
    (follow the slope to discard half)

    Statement: Given a 0-indexed integer array nums, return the index of any peak — an element strictly greater than its neighbours (nums[i] > nums[i-1] and nums[i] > nums[i+1]). O(log n).
    Example: nums=[1,2,3,1] → 2 | ⚡ n ≤ 1000, -2³¹ ≤ nums[i] ≤ 2³¹ - 1

    নোট · ফাঁকা