Find first and last index of target element from sorted array
The best way we can do this with binary search. Big O will be O(2log(n)).
Input :
int a[] = { 1, 4, 5, 7, 8, 8, 8, 9, 10 };
Target : 8
Output :
Start :4 and End :6
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
package com.omt.learn.algo; public class FirstLastIndexOfElementFromArray { public static void main(String[] args) { int a[] = { 1, 4, 5, 7, 8, 8, 8, 9, 10 }; int startEnd[] = getStartEndIndexOfTarget(a, 8); System.out.println("Start :" + startEnd[0] + " and End :" + startEnd[1]); } public static int[] getStartEndIndexOfTarget(int a[], int target) { int start = 0; int end = a.length - 1; int result[] = new int[2]; result[0] = -1; result[1] = -1; while (end > start) { int middle = start + (end - start) / 2; // this is to avoid // overflow. if (a[middle] < target) { start = middle + 1; } else if (a[middle] > target) { end = middle - 1; } else { result[0] = middle; end = middle - 1; } } if (result[0] > -1) { start = result[0]; end = a.length - 1; while (end > start) { int middle = start + (end - start) / 2; // this is to avoid // overflow. if (a[middle] < target) { start = middle + 1; } else if (a[middle] > target) { end = middle - 1; } else { result[1] = middle; start = middle + 1; } } } return result; } } |