Interview Prepmodified-binary-searchmediumAmazonGoogleMicrosoft

Search a 2D Matrix II (Staircase)

Choose your preparation mode4 modes available

Try It Solution Trace

▶

Steps

setup

Start searching first row

Begin the search on the first row of the matrix. Initialize the row index to 0 and prepare to perform binary search on this row.

💡 Starting with the first row sets the stage for applying binary search row by row.

Line:for row in matrix:

💡 The algorithm will iterate over each row to find the target.

setup

Initialize binary search pointers on first row

Set left pointer to 0 and right pointer to 4 (last index) for binary search on the first row.

💡 These pointers define the current search range within the row.

Line:left, right = 0, len(row) - 1

💡 Binary search starts with the entire row as the search space.

compare

Calculate mid index on first row

Calculate mid as (left + right) // 2, which is 2. This is the middle element index for comparison.

💡 Midpoint divides the search space to check the middle element.

Line:mid = (left + right) // 2

💡 Midpoint calculation is crucial for binary search to halve the search space.

compare

Compare mid element with target on first row

Compare row[mid] = 7 with target = 5. Since 7 > 5, we will move the right pointer left to mid - 1.

💡 Comparison decides which half of the array to discard.

Line:

elif row[mid] > target:
    right = mid - 1

💡 We eliminate the right half of the current search space.

compare

Calculate new mid index on first row

Calculate mid as (left + right) // 2 = (0 + 1) // 2 = 0 for the new search range.

💡 Recalculate midpoint after adjusting pointers.

Line:mid = (left + right) // 2

💡 Midpoint updates to reflect the new search space.

compare

Compare mid element with target on first row

Compare row[mid] = 1 with target = 5. Since 1 < 5, move left pointer to mid + 1 = 1.

💡 Comparison guides pointer movement to the right half.

Line:

elif row[mid] < target:
    left = mid + 1

💡 We discard the left half including mid element.

compare

Calculate new mid index on first row

Calculate mid as (left + right) // 2 = (1 + 1) // 2 = 1 for the narrowed search space.

💡 Midpoint recalculated for the last element in the search range.

Line:mid = (left + right) // 2

💡 Mid now points to the only remaining candidate element.

compare

Compare mid element with target on first row

Compare row[mid] = 4 with target = 5. Since 4 < 5, move left pointer to mid + 1 = 2.

💡 Comparison moves left pointer beyond right, ending search on this row.

Line:

elif row[mid] < target:
    left = mid + 1

💡 Search space is now empty (left > right), so target not found in this row.

setup

First row search ends, move to second row

Binary search on first row failed. Move to second row to start binary search again.

💡 The algorithm tries each row until the target is found or all rows are searched.

Line:

for row in matrix:
    if binary_search(row, target):
        return True

💡 The search continues to the next row after failure.

setup

Initialize binary search pointers on second row

Set left pointer to 0 and right pointer to 4 for binary search on the second row.

💡 Reset pointers for new row search.

Line:left, right = 0, len(row) - 1

💡 Binary search restarts with full row range.

compare

Calculate mid index on second row

Calculate mid as (0 + 4) // 2 = 2 for the second row.

💡 Midpoint divides the search space again.

Line:mid = (left + right) // 2

💡 Midpoint guides the next comparison.

compare

Compare mid element with target on second row

Compare row[mid] = 8 with target = 5. Since 8 > 5, move right pointer to mid - 1 = 1.

💡 Discard right half since mid element is too large.

Line:

elif row[mid] > target:
    right = mid - 1

💡 Search space shrinks to left half.

compare

Calculate new mid index on second row

Calculate mid as (0 + 1) // 2 = 0 for the reduced search space.

💡 Midpoint recalculated for smaller range.

Line:mid = (left + right) // 2

💡 Mid now points to the first element in the current range.

compare

Compare mid element with target on second row

Compare row[mid] = 2 with target = 5. Since 2 < 5, move left pointer to mid + 1 = 1.

💡 Discard left half including mid element.

Line:

elif row[mid] < target:
    left = mid + 1

💡 Search space narrows to a single element at index 1.

compare

Calculate new mid index on second row

Calculate mid as (1 + 1) // 2 = 1 for the last element in the search space.

💡 Midpoint now points to the only remaining candidate.

Line:mid = (left + right) // 2

💡 Mid points to the element to be compared next.

compare

Compare mid element with target on second row

Compare row[mid] = 5 with target = 5. They are equal, so the target is found.

💡 Finding the target ends the search successfully.

Line:

if row[mid] == target:
    return True

💡 Binary search successfully locates the target.

reconstruct

Return true and end search

Since the target was found in the second row, the function returns true and the search ends.

💡 The algorithm stops as soon as the target is found.

Line:return True

💡 Early termination optimizes the search.

def binary_search(row, target):
    left, right = 0, len(row) - 1  # STEP 2,10
    while left <= right:  # STEP 3,5,7,11,13,15
        mid = (left + right) // 2  # STEP 3,5,7,11,13,15
        if row[mid] == target:  # STEP 16
            return True  # STEP 16,17
        elif row[mid] < target:  # STEP 6,8,14
            left = mid + 1  # STEP 6,8,14
        else:
            right = mid - 1  # STEP 4,12
    return False

def searchMatrix(matrix, target):  # STEP 1,9
    for row in matrix:
        if binary_search(row, target):
            return True
    return False

if __name__ == '__main__':
    matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
    target = 5
    print(searchMatrix(matrix, target))  # Expected: True

📊

Search a 2D Matrix II (Staircase) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how binary search efficiently narrows down the search space in a sorted row.

Step 1/17

·Active fill★Answer cell

setup