Count Occurrences of Element in Sorted Array in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main advantage of using binary search to count occurrences of an element in a sorted array?

Binary search helps find the first and last positions of the element quickly, reducing time complexity from O(n) to O(log n).

intermediate

How do you find the first occurrence of an element using binary search?

Modify binary search to continue searching in the left half even after finding the element, until the first position is found.

intermediate

How do you find the last occurrence of an element using binary search?

Modify binary search to continue searching in the right half even after finding the element, until the last position is found.

beginner

What is the formula to calculate the count of occurrences once first and last positions are found?

Count = (last occurrence index) - (first occurrence index) + 1

beginner

Why is it important that the array is sorted for this method?

Because binary search requires a sorted array to correctly find positions of elements efficiently.

What is the time complexity of counting occurrences using binary search in a sorted array?

A O(n)

B O(n log n)

C O(log n)

D O(1)

Binary search finds first and last occurrences in O(log n) time each, so total is O(log n).

If the first occurrence of element 5 is at index 2 and last occurrence is at index 4, what is the count of 5 in the array?

A 3

B 2

C 1

D 4

Count = 4 - 2 + 1 = 3

Which of these is NOT a step in counting occurrences using binary search?

A Sort the array again

B Find last occurrence

C Calculate count using indices

D Find first occurrence

The array must already be sorted; no need to sort again.

What happens if the element is not present in the array?

A Count is negative

B Count is one

C Algorithm fails

D Count is zero

If element is not found, count is zero.

Why can't we use linear search to count occurrences in a sorted array efficiently?

A Linear search only works on unsorted arrays

B Linear search is slower with O(n) time

C Linear search changes the array

D Linear search requires extra memory

Linear search takes O(n) time, which is slower than binary search's O(log n).

Explain how to use binary search to count the occurrences of an element in a sorted array.

Think about finding boundaries of the element's positions.

Describe why binary search is preferred over linear search for counting occurrences in a sorted array.

Focus on time complexity and array sorting.