Find index of first occurrence when an unsorted array is sorted
Given an unsorted array and a number x, find an index of first occurrence of x when we sort the array. If x is not present, print -1.
Examples:
Input : arr[] = {10, 30, 20, 50, 20} x = 20 Output : 1 Sorted array is {10, 20, 20, 30, 50} Input : arr[] = {10, 30, 20, 50, 20} x = 60 Output : -1 60 is not present in array.
A simple solution is to first sort the array, then do binary search to find first occurrence.
Implementation:
C++
// C++ program to find index of first // occurrence of x when array is sorted. #include <bits/stdc++.h> using namespace std; int findFirst( int arr[], int n, int x) { sort(arr, arr + n); // lower_bound returns iterator pointing to // first element that does not compare less // to x. int * ptr = lower_bound(arr, arr + n, x); // If x is not present return -1. return (*ptr != x) ? -1 : (ptr - arr); } int main() { int x = 20, arr[] = { 10, 30, 20, 50, 20 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findFirst(arr, n, x); return 0; } |
Java
// Java program to find index of first // occurrence of x when array is sorted. import java.util.*; class GFG { static int findFirst( int arr[], int n, int x) { Arrays.sort(arr); // lower_bound returns iterator pointing to // first element that does not compare less // to x. int ptr = lowerBound(arr, 0 , n, x); // If x is not present return -1. return (arr[ptr] != x) ? - 1 : (ptr); } static int lowerBound( int [] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2 ; if (element > a[middle]) low = middle + 1 ; else high = middle; } return low; } // Driver Code public static void main(String[] args) { int x = 20 , arr[] = { 10 , 30 , 20 , 50 , 20 }; int n = arr.length; System.out.println(findFirst(arr, n, x)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find index of first # occurrence of x when array is sorted. import math def findFirst(arr, n, x): arr.sort() # lower_bound returns iterator pointing to # first element that does not compare less # to x. ptr = lowerBound(arr, 0 , n, x) # If x is not present return -1. return 1 if (ptr ! = x) else (ptr - arr) def lowerBound(a, low, high, element): while (low < high): middle = low + (high - low) / / 2 if (element > a[middle]): low = middle + 1 else : high = middle return low # Driver Code if __name__ = = '__main__' : x = 20 arr = [ 10 , 30 , 20 , 50 , 20 ] n = len (arr) print (findFirst(arr, n, x)) # This code is contributed by Rajput-Ji |
C#
// C# program to find index of first // occurrence of x when array is sorted. using System; class GFG { static int findFirst( int [] arr, int n, int x) { Array.Sort(arr); // lower_bound returns iterator pointing to // first element that does not compare less // to x. int ptr = lowerBound(arr, 0, n, x); // If x is not present return -1. return (arr[ptr] != x) ? -1 : (ptr); } static int lowerBound( int [] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low; } // Driver Code static public void Main() { int x = 20; int [] arr = { 10, 30, 20, 50, 20 }; int n = arr.Length; Console.Write(findFirst(arr, n, x)); } } // This code is contributed by ajit. |
PHP
<?php //PHP program to find index of first // occurrence of x when array is sorted. function findFirst( $arr , $n , $x ) { sort( $arr ); // lower_bound returns iterator pointing to // first element that does not compare less // to x. $ptr = floor ( $arr ); // If x is not present return -1. return ( $ptr != $x )? 1 : ( $ptr - $arr ); } //Code driven $x = 20; $arr = array (10, 30, 20, 50, 20); $n = sizeof( $arr )/sizeof( $arr [0]); echo findFirst( $arr , $n , $x ); #This code is contributed by Tushil. ?> |
Javascript
<script> // Javascript program to find index of first // occurrence of x when array is sorted. function findFirst(arr, n, x) { arr.sort(); // lower_bound returns iterator pointing // to first element that does not compare // less to x. let ptr = lowerBound(arr, 0, n, x); // If x is not present return -1. return (arr[ptr] != x) ? -1 : (ptr); } function lowerBound(a, low, high, element) { while (low < high) { let middle = low + parseInt( (high - low) / 2, 10); if (element > a[middle]) low = middle + 1; else high = middle; } return low; } // Driver code let x = 20; let arr = [ 10, 30, 20, 50, 20 ]; let n = arr.length; document.write(findFirst(arr, n, x)); // This code is contributed by mukesh07 </script> |
Output
1
Complexity Analysis:
- Time Complexity : O(n Log n)
- Auxiliary Space: O(1)
An efficient solution is to simply count smaller elements than x.
Implementation:
C++
// C++ program to find index of first // occurrence of x when array is sorted. #include <bits/stdc++.h> using namespace std; int findFirst( int arr[], int n, int x) { int count = 0; bool isX = false ; for ( int i = 0; i < n; i++) { if (arr[i] == x) isX = true ; else if (arr[i] < x) count++; } return (isX == false ) ? -1 : count; } int main() { int x = 20, arr[] = { 10, 30, 20, 50, 20 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findFirst(arr, n, x); return 0; } |
Java
// Java program to find index of first // occurrence of x when array is sorted. public class GFG { static int findFirst( int arr[], int n, int x) { int count = 0 ; boolean isX = false ; for ( int i = 0 ; i < n; i++) { if (arr[i] == x) { isX = true ; } else if (arr[i] < x) { count++; } } return (isX == false ) ? - 1 : count; } // Driver main public static void main(String[] args) { int x = 20 , arr[] = { 10 , 30 , 20 , 50 , 20 }; int n = arr.length; System.out.println(findFirst(arr, n, x)); } } /*This code is contributed by PrinciRaj1992*/ |
Python3
# Python 3 program to find index # of first occurrence of x when # array is sorted. def findFirst(arr, n, x): count = 0 isX = False for i in range (n): if (arr[i] = = x): isX = True elif (arr[i] < x): count + = 1 return - 1 if (isX = = False ) else count # Driver Code if __name__ = = "__main__" : x = 20 arr = [ 10 , 30 , 20 , 50 , 20 ] n = len (arr) print (findFirst(arr, n, x)) # This code is contributed # by ChitraNayal |
C#
// C# program to find index of first // occurrence of x when array is sorted. using System; public class GFG { static int findFirst( int [] arr, int n, int x) { int count = 0; bool isX = false ; for ( int i = 0; i < n; i++) { if (arr[i] == x) { isX = true ; } else if (arr[i] < x) { count++; } } return (isX == false ) ? -1 : count; } // Driver main public static void Main() { int x = 20; int [] arr = { 10, 30, 20, 50, 20 }; int n = arr.Length; Console.WriteLine(findFirst(arr, n, x)); } } /*This code is contributed by PrinciRaj1992*/ |
PHP
<?php // PHP program to find index of first // occurrence of x when array is sorted. function findFirst( $arr , $n , $x ) { $count = 0; $isX = false; for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] == $x ) $isX = true; else if ( $arr [ $i ] < $x ) $count ++; } return ( $isX == false)? -1 : $count ; } // Driver Code $x = 20; $arr = array (10, 30, 20, 50, 20); $n = sizeof( $arr ); echo findFirst( $arr , $n , $x ); // This code is contributed // by Akanksha Rai ?> |
Javascript
<script> // JavaScript program to find index of first // occurrence of x when array is sorted. function findFirst(arr, n, x) { var count = 0; var isX = false ; for ( var i = 0; i < n; i++) { if (arr[i] == x) { isX = true ; } else if (arr[i] < x) { count++; } } return (isX == false ) ? -1 : count; } // Driver Code var x = 20, arr = [ 10, 30, 20, 50, 20 ]; var n = arr.length; document.write(findFirst(arr, n, x)); // This code is contributed by Khushboogoyal499 </script> |
Output
1
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)