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.
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.
Complexity Analysis
Linear Search:
- Time Complexity: O(n) in the worst case (where n is the size of the array).
- Space Complexity: O(1).
Binary Search:
- Time Complexity: O(log n) in the worst case.
- Space Complexity: O(1).
Points to Remember
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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
Can linear search and binary search handle duplicate elements in the array?
Yes, both linear search and binary search can handle duplicate elements and will locate the first occurrence of the target element.
Question 2.
Are there scenarios where linear search is preferable over binary search?
Linear search is simpler to implement and suitable for small arrays or when the array is not sorted. It’s less efficient for large sorted arrays compared to binary search.
Question 3.
How do I handle cases where the target element is not found in the sorted array?
In both linear search and binary search, if the target element is not found, you should return an appropriate value (e.g., -1) to indicate its absence.
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
