Find first and last index of target element from sorted array
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; } } |
