First and Last Occurrence of Element in DSA C - Deep Dive

Overview - First and Last Occurrence of Element

What is it?

Finding the first and last occurrence of an element means locating the earliest and latest positions where that element appears in a list or array. This helps us understand where a value starts and ends in a sequence. We usually work with sorted or unsorted arrays to find these positions. The goal is to find these positions efficiently without checking every element one by one.

Why it matters

Without knowing the first and last occurrence, we might waste time searching the entire list repeatedly or miss important information about the range of values. For example, in searching logs or records, knowing where a value starts and ends helps in quick data retrieval and analysis. This concept saves time and computing power, making programs faster and more efficient.

Where it fits

Before this, you should understand arrays and basic searching methods like linear search and binary search. After mastering this, you can learn about frequency counting, range queries, and advanced searching algorithms like segment trees or binary indexed trees.

Mental Model

Core Idea

The first and last occurrence of an element mark the boundaries of where that element appears in a sequence, and finding them efficiently means narrowing down the search instead of scanning everything.

Think of it like...

Imagine a bookshelf with many copies of the same book scattered. Finding the first and last occurrence is like spotting the first and last copy of that book on the shelf without checking every single book.

Array: [1, 2, 2, 2, 3, 4, 4, 5]
Element: 2
Positions: 0 1 2 3 4 5 6 7
First occurrence of 2 -> index 1
Last occurrence of 2 -> index 3

Search process:
Start -> middle -> narrow down -> find boundaries

Build-Up - 7 Steps

1

Foundation

Understanding Array and Element Positions

Concept: Learn what an array is and how elements are positioned by index.

An array is a list of elements stored one after another. Each element has a position called an index, starting from 0. For example, in [5, 3, 7], 5 is at index 0, 3 at index 1, and 7 at index 2. Knowing this helps us find where elements are located.

Result

You can identify the position of any element by its index number.

Understanding indexing is essential because all searching depends on knowing where elements live in the array.

2

Foundation

Simple Linear Search for Occurrences

Concept: Use a basic method to find first and last occurrence by checking each element.

To find the first occurrence, start from the beginning and move forward until you find the element. For the last occurrence, start from the end and move backward until you find it. This method checks each element one by one.

Result

For array [1,2,2,3], first occurrence of 2 is index 1, last occurrence is index 2.

Linear search is easy to understand but can be slow for large arrays because it checks every element.

3

Intermediate

Binary Search Basics for Sorted Arrays

Concept: Learn how binary search quickly finds an element in a sorted array by dividing the search space.

Binary search looks at the middle element of a sorted array. If the middle is the target, it stops. If the target is smaller, it searches the left half; if larger, the right half. This repeats until the element is found or the search space is empty.

Result

In [1,2,3,4,5], searching for 3 finds it at index 2 quickly without checking all elements.

Binary search reduces search time from checking all elements to just a few steps by halving the search space each time.

4

Intermediate

Modified Binary Search for First Occurrence

🤔Before reading on: Do you think normal binary search can directly find the first occurrence of a repeated element? Commit to yes or no.

Concept: Adjust binary search to continue searching left even after finding the element to find the first occurrence.

When binary search finds the element, it doesn't stop. Instead, it moves left to check if the element appears earlier. It keeps updating the answer until no earlier occurrence is found.

Result

For [1,2,2,2,3], first occurrence of 2 is index 1 found by moving left after initial find.

Knowing to continue searching left after a match helps find the earliest position, not just any match.

5

Intermediate

Modified Binary Search for Last Occurrence

🤔Before reading on: Should the search move left or right after finding the element to find the last occurrence? Commit to your answer.

Concept: Adjust binary search to continue searching right after finding the element to find the last occurrence.

When binary search finds the element, it moves right to check if the element appears later. It updates the answer until no later occurrence is found.

Result

For [1,2,2,2,3], last occurrence of 2 is index 3 found by moving right after initial find.

Continuing the search right after a match ensures finding the latest position of the element.

6

Advanced

Combining First and Last Occurrence Efficiently

🤔Before reading on: Is it better to run two separate binary searches or one combined search to find both occurrences? Commit to your answer.

Concept: Run two separate modified binary searches: one for first occurrence and one for last occurrence, each efficient and clear.

Perform the first occurrence search to find the earliest index, then perform the last occurrence search to find the latest index. Both use modified binary search logic. This approach is simple and runs in O(log n) time.

Result

For [1,2,2,2,3], first occurrence is 1, last occurrence is 3 found efficiently.

Splitting the problem into two clear searches keeps code simple and performance optimal.

7

Expert

Handling Edge Cases and Unsorted Arrays

🤔Before reading on: Can binary search be used directly on unsorted arrays to find occurrences? Commit to yes or no.

Concept: Binary search requires sorted arrays; for unsorted arrays, linear search or sorting first is needed. Also, handle cases where element is absent or array is empty.

If the array is unsorted, binary search won't work correctly. You can either sort the array first (which takes time) or use linear search. Also, if the element is not present, return -1 for both occurrences. Handle empty arrays by returning -1 immediately.

Result

For unsorted [3,2,1,2], linear search finds first occurrence of 2 at index 1 and last at index 3. For missing element, both are -1.

Knowing the limitations of binary search prevents wrong assumptions and bugs in real applications.

Under the Hood

Binary search works by repeatedly dividing the search space in half. It compares the target with the middle element and decides which half to keep searching. Modified binary search for first and last occurrence adds checks to continue searching left or right after finding the target, updating the answer each time. This uses the sorted property of arrays to guarantee correctness and efficiency.

Why designed this way?

Binary search was designed to reduce search time from linear to logarithmic by exploiting sorted order. The modifications for first and last occurrence were added to handle duplicates, which normal binary search does not distinguish. Alternatives like linear search are simpler but slower. The design balances speed and simplicity.

Initial array (sorted):
[1, 2, 2, 2, 3, 4, 5]

Search for 2:
Start: low=0, high=6
Middle: mid=3 (value=2) -> found target
For first occurrence: move high=mid-1=2 to search left
For last occurrence: move low=mid+1=4 to search right
Repeat until boundaries found.

Myth Busters - 4 Common Misconceptions

Quick: Does normal binary search always find the first occurrence of a repeated element? Commit yes or no.

Common Belief: Normal binary search returns the first occurrence of the element automatically.

Reality: Normal binary search returns any occurrence, not necessarily the first or last.

Why it matters: Assuming it finds the first occurrence can cause bugs when duplicates exist, leading to wrong index results.

Quick: Can binary search be used on unsorted arrays? Commit yes or no.

Common Belief: Binary search works on any array regardless of order.

Reality: Binary search only works correctly on sorted arrays.

Why it matters: Using binary search on unsorted arrays gives incorrect results and wastes time debugging.

Quick: If an element is not in the array, does binary search return -1? Commit yes or no.

Common Belief: Binary search always returns -1 if element is missing.

Reality: Binary search returns -1 only if implemented to do so; otherwise, it may return invalid indices or no result.

Why it matters: Not handling missing elements properly can cause crashes or wrong outputs.

Quick: Is it faster to find both first and last occurrence in one binary search pass? Commit yes or no.

Common Belief: One binary search can find both first and last occurrence simultaneously.

Reality: Two separate modified binary searches are needed for clarity and correctness.

Why it matters: Trying to combine both in one pass complicates code and risks errors.

Expert Zone

1

Modified binary search uses inclusive and exclusive boundaries carefully to avoid infinite loops or missing elements.

2

Edge cases like all elements being the target or none require special handling to avoid incorrect indices.

3

In some languages or systems, integer overflow in mid calculation (mid = low + (high - low)/2) must be avoided for correctness.

When NOT to use

Avoid binary search for first and last occurrence if the array is unsorted or very small; linear search is simpler and sometimes faster. For dynamic data with frequent insertions, consider balanced trees or hash maps for occurrence tracking.

Production Patterns

In real systems, first and last occurrence searches are used in log analysis, database indexing, and search engines to quickly find ranges of data. They are often combined with caching and pre-processing for speed.

Connections

Binary Search Tree

Builds-on

Understanding binary search helps grasp how binary search trees organize data for fast lookup and range queries.

Range Queries in Segment Trees

Builds-on

Finding first and last occurrences is a simple form of range query, which segment trees generalize for complex data.

Signal Processing - Edge Detection

Analogy in different field

Detecting first and last occurrence is like finding edges in signals, marking where changes start and end.

Common Pitfalls

#1 Using normal binary search to find first occurrence without modification.

Wrong approach:

int binarySearch(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}

Correct approach:

int firstOccurrence(int arr[], int n, int x) {
int low = 0, high = n - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
result = mid;
high = mid - 1; // move left to find earlier occurrence
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}

Root cause:

Not realizing that normal binary search stops at any match, missing earlier duplicates.

#2 Applying binary search on unsorted array.

Wrong approach:

int binarySearch(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Used on arr = [3,1,4,2], which is unsorted

Correct approach:

int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) return i;
}
return -1;
}
// Or sort array first before binary search

Root cause:

Misunderstanding that binary search requires sorted data.

#3 Not handling element not found case properly.

Wrong approach:

int firstOccurrence(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
// Missing return -1 here
}

Correct approach:

int firstOccurrence(int arr[], int n, int x) {
int low = 0, high = n - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
result = mid;
high = mid - 1;
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}

Root cause:

Forgetting to return a special value when element is absent.

Key Takeaways

First and last occurrence help find the exact range of an element in a sequence efficiently.

Binary search must be modified to find first or last occurrence in sorted arrays with duplicates.

Binary search only works on sorted arrays; otherwise, use linear search or sort first.

Handling edge cases like missing elements and empty arrays is crucial for robust code.

Splitting the problem into two searches keeps code simple and performance optimal.

Practice

1. What does the term first occurrence of an element in an array mean?

easy

A. The last index where the element appears

B. The total count of the element in the array

C. The index of the first time the element appears in the array

D. The sum of all elements before the element

Solution

1. Step 1: Understand the meaning of first occurrence

   The first occurrence means the earliest position where the element is found in the array, starting from index 0.

2. Step 2: Compare options with definition

   The index of the first time the element appears in the array matches this definition exactly, while others describe different concepts.

3. Final Answer:

   The index of the first time the element appears in the array -> Option C

4. Quick Check:

   First occurrence = first index found [OK]

Hint: First occurrence means earliest index found [OK]

Common Mistakes:

• Confusing first occurrence with count of element
• Mixing first occurrence with last occurrence
• Thinking it means sum or total

2. Which of the following C code snippets correctly finds the first occurrence of x in array arr of size n?

easy

A. for(int i=0; i

B. for(int i=n-1; i>=0; i--) { if(arr[i] == x) return i; } return -1;

C. int i=0; while(arr[i] != x) i++; return i;

D. for(int i=0; i

Solution

1. Step 1: Analyze each code snippet

   for(int i=0; i

2. Step 2: Check other options for correctness

   for(int i=n-1; i>=0; i--) { if(arr[i] == x) return i; } return -1; searches from end, so it finds last occurrence. int i=0; while(arr[i] != x) i++; return i; may cause out-of-bound error if x not found. for(int i=0; i

3. Final Answer:

   for(int i=0; i -> Option A

4. Quick Check:

   Start to end loop with match check = for(int i=0; i

Hint: Loop from start, return index on first match [OK]

Common Mistakes:

• Looping backward for first occurrence
• Not handling element not found case
• Returning wrong index when element differs

3. What will be the output of the following C code?

int arr[] = {2, 4, 6, 4, 8};
int n = 5, x = 4;
int first = -1, last = -1;
for(int i=0; i

medium

A. 1 3

B. 3 1

C. 0 4

D. -1 -1

Solution

1. Step 1: Trace the loop to find first and last occurrence

   Array: [2,4,6,4,8], x=4. Loop i=0 to 4:
   i=0: arr[0]=2 !=4, skip
   i=1: arr[1]=4 ==4, first=-1 so first=1, last=1
   i=2: arr[2]=6 !=4, skip
   i=3: arr[3]=4 ==4, first=1 (unchanged), last=3
   i=4: arr[4]=8 !=4, skip

2. Step 2: Print first and last

   first=1, last=3

3. Final Answer:

   1 3 -> Option A

4. Quick Check:

   First=1, Last=3 indexes for 4 [OK]

Hint: Track first when unset, update last on every match [OK]

Common Mistakes:

• Swapping first and last values
• Not updating last occurrence
• Ignoring first occurrence initialization

4. Identify the error in the following code that tries to find the last occurrence of x in array arr of size n:

int lastOccurrence(int arr[], int n, int x) {
  int last = -1;
  for(int i=0; i

medium

A. Loop should run from n-1 to 0 for last occurrence

B. Using assignment (=) instead of comparison (==) in if condition

C. Variable last should be initialized to 0

D. Return statement should be inside the loop

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses single '=' which is assignment, not comparison. This causes wrong behavior.

2. Step 2: Correct the condition

   It should be 'if(arr[i] == x)' to compare values properly.

3. Final Answer:

   Using assignment (=) instead of comparison (==) in if condition -> Option B

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' for comparison, '=' is assignment [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Loop direction confusion for last occurrence
• Wrong initialization of variables

5. Given a sorted array arr of size n with possible duplicates, which approach is the most efficient to find the first and last occurrence of element x?

hard

A. Sort the array again and then find occurrences

B. Traverse the array from start to end once to find both occurrences

C. Use linear search twice: once from start, once from end

D. Use two binary searches: one for first occurrence, one for last occurrence

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, binary search can be used to find positions efficiently.

2. Step 2: Use binary search twice

   One binary search finds the first occurrence by moving left on matches, another finds last occurrence by moving right on matches.

3. Final Answer:

   Use two binary searches: one for first occurrence, one for last occurrence -> Option D

4. Quick Check:

   Sorted array + binary search = fastest method [OK]

Hint: Use binary search twice on sorted array [OK]

Common Mistakes:

• Using linear search on sorted array (slow)
• Sorting array again unnecessarily
• Not using binary search for efficiency