Find first and last position

Problem

Given an ascending sorted integer array, find the first and last position of a target number. If target is not in the array, return [-1, -1]

For example, given an array [1, 3, 6, 8, 8, 9] and target 8, the program should output [3, 4], if the target is 6, the program should output [-1, -1]

Solution

Solution 1:

brutal force solution is to iterate the array, when the first match is found, we register the first position, then keep moving right, detect the first position that is not equal to target, then register the last position. A few edge conditions should be considered, such as the first and last positions are the same, the target is at the end of the array, the target is at the beginning of the array, the whole array only has target, the whole array is size 1 and 2.

class TargetFinder {
  private static final int TARGET = 8;
  public static int[] findFirstAndLast(int[] a) {
    int first = -1;
    int last = -1;
    for(int i = 0; i < a.length; i++) {
      if(a[i] == TARGET && first == -1) {
        first = i;
      }
      if(first != -1 && a[i] != TARGET) {
        last = i - 1;
        break;
      }
    }
    if(first != -1 && last == -1) last = a.length - 1;
    return new int[]{first, last};
  }
  public static void main(String...args) {
    int[] a = new int[]{5,7,7,8,8,10};
    int[] result = findFirstAndLast(a);
    System.out.println("[" + result[0] + "," + result[1] + "]");
  }
}

The time complexity is O(N) and space complexity is O(1)

Solution 2:

The array is sorted, so we don't have to iterate the array, we can do binary search. One strategy that will not work is to use binary search to find a match, then search left and right in order to detect the boundary. In case the whole array matches the target, the performance degrade to O(N). We need to use binary search to find both left and right boundary. The binary search won't stop when finding the target, it will continue until the boundary is detected.
....8 8 8 8...
    l         h
       m
When searching for left boundary, whenever mid hit target, we move hi to mid, then calculate the mid again. Repeat, until hi and lo point to the same position, the left boundary is found.

When searching for right boundary, whenever mid hit target, we move lo to mid, then calculate the mid again. Repeat, until hi and lo point to the same position, the left boundary is found.

class TargetFinder {
  private static final int TARGET = 8;
  //5,7,7,8,8,10
  //      l h
  //      m  (mid won't change)
  public static int findLast(int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    int lastMid = Integer.MIN_VALUE;
    while(lo < hi) {
      int mid = lo + (hi - lo)/2; 
      if(lastMid == mid) mid++;  //lo + (1)/2 = lo special case, mid won't change, we need to break the dead loop
      if(a[mid] < TARGET) lo = mid + 1;
      else if(a[mid] > TARGET) hi = mid - 1;
      else {
        lo = mid;
      }
      lastMid = mid;
    }
    if(a[lo] == TARGET) return lo;
    else return -1;
  }
  //5,7,7,8,8,10
  //      l
  //           h
  //    m
  public static int findFirst(int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    while(lo < hi) {
      int mid = lo + (hi - lo)/2;
      if(a[mid] < TARGET) lo = mid + 1;
      else if(a[mid] > TARGET) hi = mid - 1;
      else {
        hi = mid;
      }
    }
    if(a[lo] == TARGET) return lo;
    else return -1;
  }

  public static void main(String...args) {
    int[] a = new int[]{5,7,7,8,8,10};
    System.out.println("[" + findFirst(a) + "," + findLast(a) + "]");
  }
}

The time cost is O(logN), the space cost is O(1)