0 votes
38 views
in Data Structure And Algorithm by (3.9k points)
Find first or leftmost positions of an element in a sorted array ?

1 Answer

0 votes
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

Share:- Whatsapp Facebook Facebook


Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Categories

...