Search in Rotated Sorted Array

▶

Steps

setup

Initialize pivot search boundaries

Set initial low and high pointers to cover the entire array for pivot finding.

💡 We start by searching for the pivot index where the smallest element is located, which helps split the array.

Line:

low, high = 0, len(nums) - 1

💡 The entire array is considered initially to find the rotation point.

compare

Calculate mid for pivot search

Calculate mid index as the midpoint between low and high for pivot comparison.

💡 Midpoint helps us decide which half contains the smallest element.

Line:

mid = (low + high) // 2

💡 Mid is at index 3, value 7, to compare against high value.

compare

Compare mid value to high for pivot search

Since nums[mid] (7) is greater than nums[high] (2), the pivot must be to the right of mid.

💡 If mid value is greater than high value, smallest element is in the right half.

Line:

if nums[mid] > nums[high]:
    low = mid + 1

💡 Eliminate left half including mid, pivot is in right half.

compare

Calculate new mid for pivot search

Calculate mid index between new low and high to continue pivot search.

💡 We keep narrowing down the search space to find the smallest element.

Line:

mid = (low + high) // 2

💡 Mid is now index 5, value 1, to compare with high value 2.

compare

Compare mid value to high for pivot search

Since nums[mid] (1) is less than or equal to nums[high] (2), the pivot is at mid or to the left.

💡 If mid value is less or equal to high value, smallest element is in left half including mid.

Line:

else:
    high = mid

💡 Eliminate right half after mid, pivot is in left half including mid.

compare

Calculate new mid for pivot search

Calculate mid index between low and high to continue pivot search.

💡 We continue narrowing down to find the exact pivot index.

Line:

mid = (low + high) // 2

💡 Mid is now index 4, value 0, to compare with high value 1.

compare

Compare mid value to high for pivot search

Since nums[mid] (0) is less than or equal to nums[high] (1), the pivot is at mid or to the left.

💡 We continue to narrow the search space to the left half including mid.

Line:

else:
    high = mid

💡 Eliminate right half after mid, pivot is at or before mid.

setup

Pivot found at index 4

Low equals high, so pivot index is found at 4 where the smallest element 0 is located.

💡 Finding the pivot splits the array into two sorted subarrays for targeted search.

Line:

return low

💡 Pivot index 4 divides the rotated array into two sorted parts.

decision

Determine which subarray to search

Check if target 0 lies between nums[pivot] (0) and nums[end] (2). Since it does, search right subarray from pivot to end.

💡 Choosing the correct subarray reduces search space and ensures binary search works correctly.

Line:

if nums[pivot] <= target <= nums[-1]:
    return binary_search(nums, pivot, len(nums) - 1, target)

💡 Target is in the sorted right half after pivot.

setup

Initialize binary search in right subarray

Set low and high pointers to pivot and end of array for binary search.

💡 Binary search will now find the target in the sorted right half.

Line:

low, high = pivot, len(nums) - 1

💡 Search space is narrowed to indices 4 through 6.

compare

Calculate mid for binary search

Calculate mid index between low and high for binary search comparison.

💡 Midpoint helps decide if target is found or which half to continue searching.

Line:

mid = (low + high) // 2

💡 Mid is index 5, value 1, to compare with target 0.

compare

Compare mid value to target in binary search

Since nums[mid] (1) is greater than target (0), discard right half after mid.

💡 If mid value is greater than target, search left half next.

Line:

else:
    high = mid - 1

💡 Eliminate indices after mid, narrowing search to left half.

compare

Calculate new mid for binary search

Calculate mid index between low and high for next binary search step.

💡 We continue narrowing down to find the exact target index.

Line:

mid = (low + high) // 2

💡 Mid is index 4, value 0, to compare with target 0.

compare

Target found at mid index

nums[mid] equals target, so the target is found at index 4.

💡 Finding the target ends the search successfully.

Line:

if nums[mid] == target:
    return mid

💡 Target located at index 4 in the rotated array.

def find_pivot(nums):
    low, high = 0, len(nums) - 1  # STEP 1
    while low < high:
        mid = (low + high) // 2  # STEP 2,4,6
        if nums[mid] > nums[high]:  # STEP 3
            low = mid + 1  # STEP 3
        else:
            high = mid  # STEP 5,7
    return low  # STEP 8

def binary_search(nums, low, high, target):
    while low <= high:
        mid = (low + high) // 2  # STEP 11,13
        if nums[mid] == target:  # STEP 14
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:  # STEP 12
            high = mid - 1
    return -1

def search(nums, target):
    if not nums:
        return -1
    pivot = find_pivot(nums)
    if nums[pivot] <= target <= nums[-1]:  # STEP 9
        return binary_search(nums, pivot, len(nums) - 1, target)  # STEP 10
    else:
        return binary_search(nums, 0, pivot - 1, target)

if __name__ == '__main__':
    print(search([4,5,6,7,0,1,2], 0))  # Output: 4
    print(search([4,5,6,7,0,1,2], 3))  # Output: -1

📊

Search in Rotated Sorted Array - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the algorithm narrows down the search space efficiently in a rotated array, which is not obvious from code alone.

Target: 0

lo

4

0

5

1

6

2

7

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 0

lo

4

0

5

1

6

2

mid

7

3

0

4

1

5

hi

2

6

mid[3]=7 - compare nums[mid] (7) to nums[hi] (2)

Next: lo=0 hi=6

Target: 0

4

0

5

1

6

2

mid

7

3

lo

0

4

1

5

hi

2

6

mid[3]=7 - nums[mid] > nums[hi], move low to mid+1

Next: lo=4 hi=6

Target: 0

4

0

5

1

6

2

7

3

lo

0

4

mid

1

5

hi

2

6

mid[5]=1 - compare nums[mid] (1) to nums[hi] (2)

Next: lo=4 hi=6

Target: 0

4

0

5

1

6

2

7

3

lo

0

4

mid/hi

1

5

2

6

mid[5]=1 - nums[mid] <= nums[hi], move high to mid

Next: lo=4 hi=5

Target: 0

4

0

5

1

6

2

7

3

lo/mid

0

4

hi

1

5

2

6

mid[4]=0 - compare nums[mid] (0) to nums[hi] (1)

Next: lo=4 hi=5

Target: 0

4

0

5

1

6

2

7

3

lo/mid/hi

0

4

1

5

2

6

mid[4]=0 - nums[mid] <= nums[hi], move high to mid

Next: lo=4 hi=4

Target: 0

4

0

5

1

6

2

7

3

lo/mid/hi

0

4

1

5

2

6

mid[4]=0 - pivot found

Next: lo=4 hi=4

Target: 0

4

0

5

1

6

2

7

3

lo

0

4

1

5

hi

2

6

Next: lo=4 hi=6

Target: 0

4

0

5

1

6

2

7

3

lo

0

4

1

5

hi

2

6

Next: lo=4 hi=6

Target: 0

4

0

5

1

6

2

7

3

lo

0

4

mid

1

5

hi

2

6

mid[5]=1 - compare nums[mid] (1) to target (0)

Next: lo=4 hi=6

Target: 0

4

0

5

1

6

2

7

3

lo/hi

0

4

mid

1

5

2

6

mid[5]=1 - nums[mid] > target, move high to mid-1

Next: lo=4 hi=4

Target: 0

4

0

5

1

6

2

7

3

lo/mid/hi

0

4

1

5

2

6

mid[4]=0 - compare nums[mid] (0) to target (0)

Next: lo=4 hi=4

Target: 0

4

0

5

1

6

2

7

3

lo/mid/hi

0

4

1

5

2

6

mid[4]=0 - nums[mid] == target, found target

Next: lo=4 hi=4

Key Takeaways

✓ Finding the pivot index is crucial to split the rotated array into two sorted subarrays.

This insight is hard to see from code alone because the pivot search uses a subtle comparison between mid and high values.

✓ Deciding which subarray to search based on the target's value relative to the pivot and array end narrows the search space effectively.

Plain English explanation: The target must lie in one sorted half, so we avoid searching the entire array again.

✓ Each binary search step eliminates half the search space by comparing mid value to target, quickly converging to the answer.

The trace shows exactly how pointers move and why certain halves are discarded, which is abstract in code.

Practice

1. You are given a sorted array and need to find how many times a specific target value appears. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Binary search to find the left and right boundaries of the target

B. Linear scan through the array counting occurrences

C. Dynamic programming to count occurrences using subproblems

D. Greedy approach selecting elements until target count is found

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find boundaries efficiently.

2. Step 2: Identify optimal approach

   Binary search for left and right boundaries finds the first and last occurrence indices in O(log n) time, enabling count calculation by subtraction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step [OK]

Hint: Sorted array -> binary search boundaries [OK]

Common Mistakes:

• Using linear scan despite sorted array
• Confusing DP with counting occurrences
• Applying greedy which doesn't guarantee correctness

2. You are given an array of positive integers and a threshold value. You want to find the smallest integer divisor such that when each array element is divided by this divisor and rounded up, the sum of these results does not exceed the threshold. Which algorithmic approach guarantees finding this smallest divisor efficiently?

easy

A. Greedy approach that picks divisors based on local minimum sums without backtracking

B. Dynamic programming to explore all divisor combinations and sums

C. Binary search on the divisor value combined with a feasibility check function

D. Sorting the array and using two pointers to find the divisor

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the smallest divisor that satisfies a sum condition involving ceiling division, which is monotonic with respect to the divisor.

2. Step 2: Identify the suitable algorithmic pattern

   Binary search on the answer space (divisor values) combined with a helper feasibility function efficiently narrows down the smallest divisor by checking if a candidate divisor meets the threshold condition.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits monotonicity of feasibility -> [OK]

Hint: Monotonic feasibility suggests binary search on answer space [OK]

Common Mistakes:

• Assuming greedy local choices yield global minimum divisor
• Trying DP which is inefficient and unnecessary here
• Using sorting and two pointers which don't apply to divisor search

3. You need to compute x raised to the power n efficiently, where n can be a large integer (positive or negative). Which approach guarantees the optimal time complexity for this problem?

easy

A. Use binary exponentiation by repeatedly squaring x and reducing n by half.

B. Iteratively multiply x by itself n times in a loop.

C. Use dynamic programming to store intermediate powers and build up to x^n.

D. Use a greedy approach to multiply by the largest possible power of x at each step.

Solution

1. Step 1: Understand the problem constraints

   We want to compute x^n efficiently for large n, including negative values.

2. Step 2: Identify the optimal approach

   Binary exponentiation (fast exponentiation) reduces the number of multiplications by squaring x and halving n at each step, achieving O(log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary exponentiation is the classic optimal approach for power calculation [OK]

Hint: Binary exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking iterative multiplication is efficient for large n
• Confusing DP with binary exponentiation
• Assuming greedy approach works for powers

4. Consider the following buggy code for finding a peak element. Which line contains the subtle bug that can cause incorrect results or infinite recursion?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid]:  # Line X
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

medium

A. Line 5: if nums[mid] < nums[mid]:

B. Line 4: mid = (low + high) // 2

C. Line 3: if low == high: return low

D. Line 7: return binarySearch(low, mid)

Solution

1. Step 1: Identify suspicious comparison

   Line 5 compares nums[mid] with itself, which is always false, causing wrong recursion path.

2. Step 2: Understand impact

   This bug causes infinite recursion or incorrect peak detection because the condition never triggers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Comparison must be nums[mid] < nums[mid + 1] [OK]

Hint: Check comparisons carefully for off-by-one errors [OK]

Common Mistakes:

• Comparing mid with mid instead of mid+1
• Off-by-one causing infinite recursion
• Returning wrong index after recursion

5. Consider the following buggy code for the Koko Eating Bananas problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += pile // speed  # Line 6
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

medium

A. Line 9: Returning true when hours <= h

B. Line 3: import statement

C. Line 6: Using floor division instead of ceiling division

D. Line 14: Updating low to mid + 1

Solution

1. Step 1: Identify how hours are calculated

   Line 6 uses floor division (pile // speed), which underestimates hours needed because partial piles still require a full hour.

2. Step 2: Understand impact on feasibility

   Underestimating hours causes can_finish to return true incorrectly, leading to wrong minimum speed.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Replacing floor division with ceiling fixes the bug [OK]

Hint: Hours must be ceil(pile / speed), not floor division [OK]

Common Mistakes:

• Using floor division instead of ceiling
• Misinterpreting feasibility condition