First and Last Occurrence of Element in DSA C++ - Time & Space Complexity

Time Complexity: First and Last Occurrence of Element

O(log n)

Understanding Time Complexity

We want to know how long it takes to find the first and last positions of a number in a list.

How does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int firstOccurrence(const vector<int>& arr, int target) {
    int start = 0, end = arr.size() - 1, result = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) {
            result = mid;
            end = mid - 1;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}

int lastOccurrence(const vector<int>& arr, int target) {
    int start = 0, end = arr.size() - 1, result = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) {
            result = mid;
            start = mid + 1;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}
    

This code finds the first and last positions of a target number in a sorted list using binary search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search range each time.
• How many times: The loop runs about log base 2 of n times, where n is the list size.

How Execution Grows With Input

Each time the list size doubles, the number of steps increases by only one.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly as the list gets bigger, increasing by one each time the size doubles.

Final Time Complexity

Time Complexity: O(log n)

This means the search gets only a little slower even if the list grows a lot.

Common Mistake

[X] Wrong: "Finding first and last occurrence takes as long as checking every item one by one."

[OK] Correct: Because the list is sorted, we can jump around and cut the search area in half each time, so we don't check every item.

Interview Connect

Knowing how to quickly find positions in sorted data shows you understand efficient searching, a key skill in many coding tasks.

Self-Check

"What if the list was not sorted? How would the time complexity change?"