Find start and end index of elements in unsorted array in C++

In this problem, we are given an array aar[] containing n unsorted integer values ​​and an integer val. Our task is to find the starting and ending index of an element in an unsorted array.

For occurrences of an element in the array, we will return,

"start index and end index" (if found twice or more in the array).

"Single index" if found

"Element does not exist" if not found in the array.

Let us take an example to understand the problem,

Example 1

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
Output : starting index = 0, ending index = 5

Explanation

Element 2 appears twice,

appears for the first time at index = 0,

appears for the second time at index = 5

Example 2

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
Output : Present only once at index 2

Explanation

Element 5 appears only once at index = 2,

Example 3

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
Output : Not present in the array!

Solution

Solve this A simple approach to the problem is to iterate over the array.

We will iterate through the array and keep two index values: first and last. The first index will traverse the array from the beginning, and the last index will traverse from the end of the array. The loop ends when the elements at the first and last index have the same value.

Algorithm

• Step 1 - Loop through the array

  • Step 1.1 - Use the first index to traverse from the beginning and the last index to traverse from the end.

  • Step 1.2 - If the value at any index is equal to val. Do not increase the index value.

  • Step 1.3 - Return if the two indexes have the same value.

Example

Program that illustrates how our solution works

#include <iostream>
using namespace std;

void findStartAndEndIndex(int arr[], int n, int val) {
   int start = 0;
   int end = n -1 ;
   while(1){
   if(arr[start] != val)
      start++;
   if(arr[end] != val)
      end--;
   if(arr[start] == arr[end] && arr[start] == val)
      break;
   if(start == end)
      break;
}
   if (start == end ){
      if(arr[start] == val)
         cout<<"Element is present only once at index : "<<start;
      else
         cout<<"Element Not Present in the array";
   } else {
      cout<<"Element present twice at \n";
      cout<<"Start index: "<<start<<endl;
      cout<<"Last index: "<<end;
   }
}
int main() {
   int arr[] = { 2, 1, 5, 4, 6, 2, 9, 0, 2, 3, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int val = 2;
   findStartAndEndIndex(arr, n, val);
   return 0;
}

Output

Element present twice at
Start index: 0
Last index: 8

The above is the detailed content of Find start and end index of elements in unsorted array in C++. For more information, please follow other related articles on the PHP Chinese website!