First and Last Occurrence of Element in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find first and last occurrence of 3 in sorted array

What is the output of the following C++ code that finds the first and last occurrence of the number 3 in a sorted array?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

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

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

int main() {
    vector<int> arr = {1, 2, 3, 3, 3, 4, 5};
    int target = 3;
    cout << firstOccurrence(arr, target) << " " << lastOccurrence(arr, target) << endl;
    return 0;
}

A 1 3

B 2 4

C 3 5

D -1 -1

💡 Hint

Remember that the array is sorted and contains multiple 3s. The first occurrence is the smallest index where 3 appears, and the last occurrence is the largest index.

The first occurrence of 3 is at index 2 (0-based), and the last occurrence is at index 4. The binary search narrows down to these indices by adjusting the search space when the target is found.

❓ Predict Output

intermediate

Output when element is not present

What will be the output of the following code when searching for element 6 in the array?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

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

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

int main() {
    vector<int> arr = {1, 2, 3, 3, 3, 4, 5};
    int target = 6;
    cout << firstOccurrence(arr, target) << " " << lastOccurrence(arr, target) << endl;
    return 0;
}

A -1 -1

B 0 6

C 6 6

D 5 5

💡 Hint

If the element is not found, the functions return -1.

Since 6 is not in the array, both firstOccurrence and lastOccurrence return -1, indicating the element is absent.

🔧 Debug

advanced

Identify the bug in lastOccurrence function

The following code is intended to find the last occurrence of a target in a sorted array. What is the bug causing incorrect output?

DSA C++

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

A The result variable is not updated when arr[mid] > target.

B The mid calculation should be 'mid = (low + high + 1) / 2'.

C The function should return 'low' instead of 'result'.

D The loop condition should be 'low <= high' instead of 'low < high'.

💡 Hint

Check the loop condition carefully to ensure all elements are checked.

Using 'low < high' causes the loop to miss checking when low equals high, potentially skipping the last occurrence. Changing to 'low <= high' ensures all elements are checked.

❓ Predict Output

advanced

Output of first and last occurrence in array with single element

What is the output of the code when the array contains only one element which is the target?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

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

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

int main() {
    vector<int> arr = {7};
    int target = 7;
    cout << firstOccurrence(arr, target) << " " << lastOccurrence(arr, target) << endl;
    return 0;
}

A 0 0

B -1 -1

C 0 -1

D -1 0

💡 Hint

With only one element equal to target, both first and last occurrence are at index 0.

The single element matches the target, so both first and last occurrence indices are 0.

🧠 Conceptual

expert

Why binary search is efficient for first and last occurrence?

Why is binary search preferred over linear search to find the first and last occurrence of an element in a sorted array?

A Binary search works only on unsorted arrays, so it is faster than linear search.

B Binary search can find the exact position without checking all elements, but linear search cannot find the element.

C Binary search reduces the search space by half each step, making it O(log n), while linear search is O(n).

D Binary search uses recursion which is always faster than iteration used in linear search.

💡 Hint

Think about how many elements are checked in each method.

Binary search halves the search space each time, leading to logarithmic time complexity O(log n). Linear search checks each element one by one, leading to O(n) time.