Given a sorted array and a target, return the first and last index of the target. If it is missing, return minus 1 and minus 1, in O of log n time.
DSA Animator › DSA Revision › Binary Search › Find First and Last Position of Element
Remember: on a match, record it and keep searching toward the boundary you want. Two binary searches give the first and the last position. The video solves Find First and Last Position of Element (LeetCode 34, Medium) with the Binary Search Bounds pattern from the Binary Search topic, and you can replay every step in the interactive Find First and Last Position of Element animation.
Given a sorted array and a target, return the first and last index of the target. If it is missing, return minus 1 and minus 1, in O of log n time.
For 5, 7, 7, 8, 8, 10 and target 8, the answer is 3 and 4.
Finding one 8 and then walking left and right is O of n if there are many copies. Two binary searches keep it logarithmic.
Run binary search twice. To find the first index, when you hit the target, record it and keep searching left. To find the last index, record it and keep searching right.
First search: mid 2 holds 7, which is smaller, so low moves to 3. Mid 4 holds 8: record 4, and keep searching left. Mid 3 holds 8: record 3, and search left again, which ends the search, so the first index is 3. Second search: mid 4 holds 8, so record 4 and keep searching right. Mid 5 holds 10, which is bigger, so the search ends, and the last index is 4. The answer is 3 and 4.
In code, one helper takes a flag for first or last. On a match it records mid, then moves high left for the first, or low right for the last. Otherwise it moves like a normal binary search. Two searches, so it's O of log n time.
Remember: on a match, record it and keep searching toward the boundary you want. Two binary searches give the first and the last position.