Recall & Review
beginner
What does 'First Occurrence of Element' mean in an array?
It means the position (index) where a given element appears for the very first time when we look from the start of the array.
Click to reveal answer
beginner
What does 'Last Occurrence of Element' mean in an array?
It means the position (index) where a given element appears for the very last time when we look from the end of the array.
Click to reveal answer
intermediate
Why is binary search useful for finding first and last occurrences in a sorted array?
Because binary search quickly narrows down the search area by dividing the array in half repeatedly, making it efficient to find the exact first or last position of an element.
Click to reveal answer
beginner
In a linear search for first occurrence, what is the worst-case time complexity?
O(n), where n is the number of elements in the array, because you may need to check every element until you find the first occurrence.
Click to reveal answer
intermediate
How can you modify binary search to find the last occurrence of an element?
After finding the element, continue searching in the right half to check if the element appears later, updating the last occurrence index until no more are found.
Click to reveal answer
What is the first step to find the first occurrence of an element in a sorted array using binary search?
✗ Incorrect
In binary search for first occurrence, when you find the element, you continue searching to the left to find if it appears earlier.
If an element does not exist in the array, what should the function return when searching for first or last occurrence?
✗ Incorrect
Returning -1 or a similar value indicates the element is not found in the array.
What is the time complexity of finding first and last occurrence using binary search in a sorted array?
✗ Incorrect
Binary search runs in O(log n) time, making it efficient for this task.
Which of these is NOT a correct approach to find first occurrence of an element?
✗ Incorrect
Binary search with right side exploration is used for last occurrence, not first.
If the array is unsorted, what is the best way to find first and last occurrence?
✗ Incorrect
Binary search requires sorted arrays. For unsorted arrays, linear search is the direct method.
Explain how to find the first occurrence of an element in a sorted array using binary search.
Think about narrowing the search to the left side after finding the element.
You got /5 concepts.
Describe the difference between finding first and last occurrence of an element in a sorted array.
Focus on which side of the array to continue searching after finding the element.
You got /4 concepts.