C Program to find first and last position of element in sorted array

by on

Follow @https://twitter.com/aticleworld

4

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:

About

I am an embedded c software engineer and a corporate trainer, currently, I am working as senior software engineer in a largest Software consulting company . I have working experience of different microcontrollers (stm32, LPC, PIC AVR and 8051), drivers (USB and virtual com-port), POS device (VeriFone) and payment gateway (global and first data).

4 comments

Leave a Reply Cancel reply