# Find first or leftmost positions of an element in a sorted array ?

38 views
Find first or leftmost positions of an element in a sorted array ?

by (3.7k points)
To find first or leftmost position of an element in a sorted array. To find leftmost position in sorted array in O(logN) Time Complexity.

See the following running example with code to find leftmost position in a sorted array:-

If Code output is -1 means element not found otherwise element is exists.

package com.dev.search;

public class LeftMostIndex {

public static void main(String[] args) {
int arr[] = {2,3,3,3,3};
int x = 3;
int lIndex = findLeftMostIndex(arr, x);
System.out.println("Left Most Index: " + lIndex);
}

private static int findLeftMostIndex(int[] arr, int x) {
return findLeftMostIndex(arr, 0, arr.length-1, x);
}

//Time Complexity O(logN)
private static int findLeftMostIndex(int[] arr, int l, int h, int x) {
if(l>h) {
return -1;
}
int mid = l+(h-l)/2;
if(arr[mid]==x) {
if(mid == 0 || arr[mid-1] != x) {//mid =0 means search data placed into 0 index
return mid;
}else {
return findLeftMostIndex(arr, l, mid-1, x);
}
}else if(x > arr[mid]) {
return findLeftMostIndex(arr, mid+1, h, x);
}else if(x < arr[mid]) {
return findLeftMostIndex(arr, l, mid-1, x);
}
return -1;
}

}
Output:-

Left Most Index: 1