Find index of first occurrence when an unsorted an array is sorted
Given an unsorted an 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 an 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:
Python3
# Python3 program to find index of first# occurrence of x when an array is sorted.import mathdef 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 Codeif __name__ == '__main__':    x = 20    arr = [10, 30, 20, 50, 20]    n = len(arr)    print(findFirst(arr, n, x)) |
Output
1
An efficient solution is to simply count smaller elements than x.
Implementation:
Python3
# Python 3 program to find index# of first occurrence of x when# an 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 Codeif __name__ == "__main__":    x = 20    arr = [10, 30, 20, 50, 20]    n = len(arr)    print(findFirst(arr, n, x)) |
Output
1