First Occurrence in a Sorted Array
Introduction
Searching for the first occurrence of an element in a sorted array is a common problem in computer science and programming. When an array is sorted, it allows us to use efficient algorithms to find the first occurrence of a specific element. This page will guide you through the process of finding the element that occur first in the given set of array.
What is First Occurrence in a Sorted Array?
“First occurrence in a sorted array” refers to the index or position of the first occurrence of a specific element within an array that is sorted in ascending order. In other words, it involves finding the first position at which a particular value appears in the sorted array.
Here we have an example,
- Suppose we have a sorted array : [0, 1, 1, 2, 3, 4, 4, 4, 5, 7]
and we have to find the first occurrence of ‘4’. The first occurrence of ‘4‘ in this array is at index 5. Therefore, the “first occurrence in a sorted array” in this context refers to finding the index ‘5’ as the result.
Two Approach for 1st Occurrence in a Sorted Array
There are mainly two approaches for finding out the first occurrence in a sorted array :
Linear Search Approach (Brute Force Approach)
Binary Search Approach
Linear Search Approach
Linear search is a straightforward method for finding the first occurrence in a sorted array. It involves iterating through the array from the beginning and stopping as soon as the desired element is found.
Here’s a basic example in Python:
def first_occurrence_linear(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1 # Element not found
# Example usage:
sorted_array = [1, 2, 3, 4, 4, 5, 6, 7]
element_to_find = 4
index = first_occurrence_linear(sorted_array, element_to_find)
if index != -1:
print("The first occurrence of", element_to_find, "is at index", index)
else:
print(element_to_find, "was not found in the array.")
Output :
The first occurrence of 4 is at index 3.
Explanation:
- Iterates through each element in the array using a for loop.
- Compares each element with the target value.
- Returns the index immediately when the target is found.
- If not found, returns -1 after the loop ends.
- Time Complexity: O(n) – Scans up to all elements in the array.
- Space Complexity: O(1) – Uses constant space.
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Binary Search Approach
Binary search is a more efficient approach for sorted arrays. It works by dividing the array into halves and eliminating half of the remaining elements with each comparison.
Here’s how to use binary search to find the first occurrence:
def first_occurrence_binary(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # Search the left subarray for the first occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# Example usage:
sorted_array = [1, 2, 3, 4, 4, 5, 6, 7]
element_to_find = 4
index = first_occurrence_binary(sorted_array, element_to_find)
if index != -1:
print("The first occurrence of", element_to_find, "is at index", index)
else:
print(element_to_find, "was not found in the array.")
Output :
The first occurrence of 4 is at index 3.
Explanation:
- Performs binary search on a sorted array to find the target element.
- If target is found, stores index and searches left half for earlier occurrence.
- If middle value < target, moves search to right half; else to left half.
- Returns the first index where the target appears, or -1 if not found.
- Time Complexity: O(log n) – Binary search divides the array in half each time.
- Space Complexity: O(1) – Uses only variables, no extra data structures.
Points to Remember
When to Use This in Real Life:
- Search Logs: Finding the first time a specific user or event shows up.
- Time-Series Data: Finding the first reading that exceeds a threshold.
- Version Control: Locating the first commit where a change occurred.
- Auto complete Systems: Identifying the first matching prefix.
To wrap it up:
In this comprehensive guide on finding the first occurrence in a sorted array, we’ve explored two key approaches: linear search and binary search. Whether you’re a beginner or an experienced programmer, understanding these methods is crucial for efficient data retrieval and analysis.
FAQs
The goal is to locate the first index where a target element appears in a sorted array, even if it occurs multiple times. This is commonly done using a modified binary search.
Standard binary search stops on the first match, which could be any occurrence. To get the first occurrence, we need to continue searching on the left half after finding a match.
When a match is found, store the index and move right = mid – 1 to explore earlier positions. This ensures you get the leftmost match.
The time complexity is O(log n) because the array is sorted and we’re using binary search to narrow down the range.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
