Find First and Last Position of Element

▶

Steps

setup

Initialize pointers

Set initial search boundaries: left at 0 and right at last index. Initialize 'found' to -1 indicating target not found yet.

💡 Starting with the full array ensures the entire search space is considered.

Line:

left, right = 0, len(nums) - 1
found = -1

💡 The search space covers the entire array initially.

compare

Calculate mid index

Calculate mid as the average of left and right pointers: mid = (0 + 5) // 2 = 2.

💡 Mid divides the current search space roughly in half.

Line:

mid = (left + right) // 2

💡 Mid points to the middle element of the current search space.

compare

Compare mid value with target and move left pointer

nums[mid] = 7 is less than target 8, so move left pointer to mid + 1 = 3 to search right half.

💡 Since nums[mid] < target, discard left half to narrow search.

Line:

if nums[mid] < target:
    left = mid + 1

💡 Eliminating left half reduces search space efficiently.

compare

Calculate new mid index

Calculate mid with updated pointers: mid = (3 + 5) // 2 = 4.

💡 Mid recalculates to center of new search space.

Line:

mid = (left + right) // 2

💡 Mid moves as search space changes.

compare

Target found at mid

nums[mid] equals target (nums[4] == 8), so record found index as 4 and break binary search.

💡 Finding target stops binary search; next find full range.

Line:

if nums[mid] == target:
    found = mid
    break

💡 Binary search locates one occurrence efficiently.

compare

Compare mid value with target and move right pointer

If nums[mid] was greater than target, we would move right pointer to mid - 1. This step is added to illustrate that case for completeness.

💡 If nums[mid] > target, discard right half to narrow search.

Line:

else:
    right = mid - 1

💡 Eliminating right half reduces search space efficiently.

traverse

Initialize start and end pointers

Set start and end pointers to found index 4 to begin expanding left and right to find full range.

💡 Start expanding from found index to find first and last positions.

Line:

start, end = found, found

💡 Start and end mark current known target range.

traverse

Expand start pointer left

Check element left of start (index 3). Since nums[3] == 8, move start left to 3.

💡 Moving start left finds first occurrence of target.

Line:

while start - 1 >= 0 and nums[start - 1] == target:
    start -= 1

💡 First occurrence is at index 3.

traverse

Expand end pointer right

Check element right of end (index 5). Since nums[5] = 10 != target, stop expanding end pointer.

💡 End pointer stops when next element is not target.

Line:

while end + 1 < len(nums) and nums[end + 1] == target:
    end += 1

💡 Last occurrence is at index 4.

reconstruct

Return the final range

Return [3, 4] as the first and last positions of the target in the array.

💡 The algorithm outputs the exact range where the target appears.

Line:

return [start, end]

💡 Final answer is the continuous range of target occurrences.

def searchRange(nums, target):  # STEP 1
    left, right = 0, len(nums) - 1  # STEP 1
    found = -1  # STEP 1
    while left <= right:  # STEP 2-5
        mid = (left + right) // 2  # STEP 2,4
        if nums[mid] == target:  # STEP 5
            found = mid  # STEP 5
            break  # STEP 5
        elif nums[mid] < target:  # STEP 3
            left = mid + 1  # STEP 3
        else:  # STEP 6
            right = mid - 1  # STEP 6
    if found == -1:  # STEP 10
        return [-1, -1]  # STEP 10
    start, end = found, found  # STEP 7
    while start - 1 >= 0 and nums[start - 1] == target:  # STEP 8
        start -= 1  # STEP 8
    while end + 1 < len(nums) and nums[end + 1] == target:  # STEP 9
        end += 1  # STEP 9
    return [start, end]  # STEP 10

if __name__ == '__main__':
    print(searchRange([5,7,7,8,8,10], 8))  # Output: [3,4]

📊

Find First and Last Position of Element - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison helps you understand how binary search efficiently locates the target and how post-processing finds the exact range.

Target: 8

lo

5

0

7

1

7

2

8

3

8

4

hi

10

5

Next: lo=0 hi=5

Target: 8

lo

5

0

7

1

mid

7

2

8

3

8

4

hi

10

5

mid[2]=7 - nums[mid] < target

Next: lo=0 hi=5

Target: 8

5

0

7

1

7

2

lo

8

3

8

4

hi

10

5

Next: lo=3 hi=5

Target: 8

5

0

7

1

7

2

lo

8

3

mid

8

4

hi

10

5

mid[4]=8 - nums[mid] == target

Next: lo=3 hi=5

Target: 8

5

0

7

1

7

2

lo

8

3

mid

8

4

hi

10

5

mid[4]=8 - target found

Next: lo=3 hi=5

Target: 8

5

0

7

1

7

2

lo

8

3

8

4

hi

10

5

Next: lo=3 hi=5

Target: 8

5

0

7

1

7

2

8

3

8

4

10

5

Target: 8

5

0

7

1

7

2

8

3

8

4

10

5

Target: 8

5

0

7

1

7

2

8

3

8

4

10

5

Target: 8

5

0

7

1

7

2

8

3

8

4

10

5

Key Takeaways

✓ Binary search efficiently finds any occurrence of the target in a sorted array.

This efficiency is hard to see from code alone because the pointer updates and mid calculations happen quickly and implicitly.

✓ After finding one occurrence, expanding left and right finds the full range of the target.

This post-processing step is crucial and often overlooked when reading code without visualization.

✓ Each pointer movement and comparison reduces the search space, showing the divide-and-conquer nature of binary search.

Seeing the eliminated indices visually clarifies why binary search is O(log n).

Practice

1. Consider the following buggy feasibility check code for Capacity to Ship Packages. Which line contains the subtle bug that can cause incorrect feasibility results?

def can_ship_early_stop(weights, days, capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            current_load = 0
            if day_count > days:
                return False
        current_load += w
    return True

medium

A. Line checking if day_count exceeds days

B. Line incrementing day_count after resetting current_load

C. Line resetting current_load to 0 before incrementing day_count

D. Line adding current package weight to current_load

Solution

1. Step 1: Identify order of operations in feasibility check

   The bug is resetting current_load to 0 before incrementing day_count, which causes the current package weight to be lost.

2. Step 2: Correct approach

   Day count should increment first, then current_load reset to 0, then add current package weight to current_load.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting current_load before day_count causes lost package weight [OK]

Hint: Reset current_load after incrementing day_count and before adding weight [OK]

Common Mistakes:

• Swapping order of reset and increment
• Forgetting to increment day_count
• Adding weight before reset

2. The following code attempts to find the minimum in a rotated sorted array with duplicates. Identify the bug:

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        if nums[low] < nums[high]:
            return nums[low]
        mid = (low + high) / 2  # line 6
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            high -= 1
    return nums[low]

What is the bug?

medium

A. Line 6 uses floating point division instead of integer division for mid calculation.

B. The condition nums[low] < nums[high] should be nums[low] <= nums[high].

C. The decrement of high in the else block should be increment of low instead.

D. Returning nums[low] at the end should be returning nums[mid].

Solution

1. Step 1: Examine mid calculation

   Line 6 uses (low + high) / 2 which results in a float in Python 3, causing an error when used as an index.

2. Step 2: Impact of bug

   Using float index causes runtime error or unexpected behavior; integer division (//) is required.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid must be integer index [OK]

Hint: Mid index must be integer, not float [OK]

Common Mistakes:

• Using / instead of // for mid
• Returning nums[mid] instead of nums[low]

3. What is the time complexity of the optimal binary search solution for the Minimum Days to Make m Bouquets problem, given n flowers and day range D = maxDay - minDay?

medium

A. O(n * D) because we check each day sequentially and scan all flowers.

B. O(n log D) because binary search reduces day range and each feasibility check scans n flowers.

C. O(log n * D) because binary search is on flowers and day range is scanned.

D. O(n + D) because we combine linear scans of flowers and days.

Solution

1. Step 1: Identify outer loop complexity

   Binary search runs in O(log D) iterations, where D is the day range.

2. Step 2: Identify inner loop complexity

   Each feasibility check scans all n flowers in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Combining gives O(n log D), not O(n * D) or others. [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing linear scan over days as O(n*D)
• Mixing binary search on flowers instead of days

4. Examine the following code snippet intended to search a target in a 2D matrix using binary search treating it as a 1D array. Identify the line containing the subtle bug that can cause incorrect results or runtime errors.

medium

A. Line 6: row, col = divmod(mid, n)

B. Line 3: left, right = 0, m * n - 1

C. Line 1: m, n = len(matrix), len(matrix[0])

D. Line 9: left = mid + 1

Solution

1. Step 1: Check for empty matrix handling

   The code does not check if matrix or matrix[0] is empty before accessing len(matrix[0]), which can cause runtime errors.

2. Step 2: Verify other lines

   Lines for binary search boundaries and index mapping are correct assuming valid input.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing empty matrix check leads to crash [OK]

Hint: Always check for empty matrix or empty rows before accessing indices [OK]

Common Mistakes:

• Forgetting empty input checks
• Incorrect index mapping
• Wrong boundary updates

5. Suppose the problem is modified so that balls can be placed multiple times at the same position (reuse allowed). Which modification to the algorithm is correct to find the maximum minimum distance?

hard

A. Keep the same binary search and greedy feasibility check since reuse does not affect placement logic

B. Modify feasibility check to count balls without updating last_pos when reuse occurs

C. Replace binary search with a linear search over all distances due to reuse complexity

D. Use dynamic programming to handle multiple placements at the same position

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means multiple balls can be placed at the same position, so distance between balls can be zero.

2. Step 2: Modify feasibility check

   The greedy check must count balls even if distance is zero, but only update last_pos when distance condition is met to avoid infinite loops.

3. Step 3: Binary search remains valid

   Binary search on answer space still applies, but feasibility check logic must adapt to reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Feasibility check must handle reuse carefully [OK]

Hint: Reuse breaks distance check; feasibility must count balls differently [OK]

Common Mistakes:

• Assuming reuse doesn't change feasibility check
• Switching to linear search unnecessarily