In this blog post, we learn how to write a C program to find first and last position of element in sorted array? So here we will write the C program to find the first and last position of member in sorted array. We will also see how to display the start and ending index of an element in a sorted array using C programming.
Example,
Input1: int arr[]= {5,7,7,8,8,10}, element= 8 (array element) Output1: [3,4] //start index of 8 is 3, ending index of 8 is 4 Input2: int arr[]= {1, 3, 5, 5, 5, 5, 5,67, 123, 125}, element= 5 (array element) Output2: [2,6] //start index of 5 is 2, ending index of 5 is 6
Note: Input Array must be sorted.
Logic to find first and last position of element in sorted array
So let’s see the Logic to find the first and last position of the element in a sorted array. Suppose arr is a given sorted integer array of size N (arr[N] ), the task is to write the C program to find the starting and ending position of a given target value. If the target value is not found in the array, a message should display element is not found.
1. Create two intermediate variables firstIndex and lastIndex.
2. Initialize the small and large variable with -1.
3. Now iterate the array from the beginning. Once we find the target element we will update both firstIndex and lastIndex.
4. print both variables using the printf a library function. If the target element not found in the array display the above-mentioned message.
If you want to learn more about the C language, you can check this course, Free Trial Available.
C Program to find first and last position of element in sorted array
#include <stdio.h> //Calculate array size #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) void findFirstAndLast(int arr[], int n, int target) { int firstIndex = -1; //store first index element int lastIndex = -1; //last index of element int i = 0; //iteration for (i = 0; i < n; i++) { //target element find in array if (arr[i] == target) { if (firstIndex == -1) { //update first and last index firstIndex = i; lastIndex= i; } else { //update last index lastIndex = i; } } } if (firstIndex != -1) { printf("First Occurrence = %d\n",firstIndex); printf("Last Occurrence = %d\n",lastIndex); } else { printf("Element Not Found in Array"); } } int main() { int arr[] = {5,7,7,8,8,10}; int element= 8; const int N = ARRAY_SIZE(arr); findFirstAndLast(arr,N,element); return 0; }
Explanation: Suppose an example, we have an array 5,7,7,8,8,10} and the target is 8. Now we will start iterating from zero indexes. We will encounter 8 at the third index, so firstIndex will be 3 and lastIndex will also be 3. Now we will keep iterating the array until the end of the array. If we encounter the next 8 in the array we will update lastIndex with the array index. So here we will again encounter 8 at the fourth index, so we will update lastIndex with 4.
Using the binary search we can also solve this problem. The time complexity of the below solution is O(log n) and the auxiliary space is O(1).
#include <stdio.h> //Calculate array size #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) /* if target element is present in arr[], function returns the index of first occurrence of target element in arr[0..n-1], otherwise returns -1 */ int findFirstOccurrenceIndex(int arr[], int n, int target) { int low = 0, high = n - 1, ret = -1; while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high) / 2; if (arr[mid] > target) { // if target is less than the mid element, //discard right half high = mid - 1; } else if (arr[mid] < target) { // if target is greater than the mid element, // discard left half low = mid + 1; } else { // If arr[mid] is same as target, we // update ret and move to the left // half. ret = mid; high = mid - 1; } } return ret; } /* if target element is present in arr[], function returns the index of last occurrence of target element in arr[0..n-1], otherwise returns -1 */ int findLastOccurrenceIndex(int arr[], int n, int target) { int low = 0, high = n - 1, ret = -1; while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high) / 2; if (arr[mid] > target) { // if target is less than the mid element, //discard right half high = mid - 1; } else if (arr[mid] < target) { // if target is greater than the mid element, // discard left half low = mid + 1; } else { // If arr[mid] is same as target, we // update ret and move to the right // half. ret = mid; low = mid + 1; } } return ret; } int main() { int arr[] = {5,7,7,8,8,9,10,12}; int element= 7; const int N = ARRAY_SIZE(arr); int index = findFirstOccurrenceIndex(arr, N, element); if (index != -1) { printf("First occurrence of element %d is found at index >> %d\n\n", element, index); //Get last index index = findLastOccurrenceIndex(arr, N, element); printf("Last occurrence of element %d is found at index >> %d\n\n", element, index); } else { //if target element not found in array printf("Element not found in the array\n\n"); } return 0; }
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- C program to find odd occurring elements in an array of limited range
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
- How to access 2d array in C?
- Dangling, Void, Null and Wild Pointers
- Function pointer in c, a detailed guide
- Memory Layout in C.
- 100 C interview Questions
- File handling in C.