package kata;

import static kata.Printer.*;
import java.util.*;

/**
 * https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array
 */
public class FirstAndLastPositionOfElementInSortedArray {
  static int[] firstAndLastPositionOfElementInSortedArray(int[] nums, int target) {
	  int[] targetRange = {-1, -1};

    int leftIdx = extremeInsertionIndex(nums, target, true);

		// assert that `leftIdx` is within the array bounds and that `target`
		// is actually in `nums`.
		if (leftIdx == nums.length || nums[leftIdx] != target) {
			return targetRange;
		}

		targetRange[0] = leftIdx;
		targetRange[1] = extremeInsertionIndex(nums, target, false)-1;

		return targetRange;
  }

  // returns leftmost (or rightmost) index at which `target` should be
  // inserted in sorted array `nums` via binary search.
  private static int extremeInsertionIndex(int[] nums, int target, boolean left) {
      int lo = 0;
      int hi = nums.length;

      while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] > target || (left && target == nums[mid])) {
          hi = mid;
        }
        else {
          lo = mid+1;
        }
      }

      return lo;
  }

  public static void main(String args[]) {
    runSample(new int[]{5,7,7,8,8,10}, 8, new int[]{3, 4});
    runSample(new int[]{5,7,7,8,8,10}, 6, new int[]{-1, -1});
  }

  static void runSample(int[] nums, int target, int[] ans) {
    System.out.printf(
      "%s,%s = %s(%s)\n",
      Arrays.toString(nums),
      target,
      Arrays.toString(firstAndLastPositionOfElementInSortedArray(nums, target)),
      Arrays.toString(ans));
  }
}

@@ -363,32 +363,33 @@
 meInsertionIndex
+2
 (nums, target, t
@@ -526,16 +526,34 @@
 ength %7C%7C
+ leftIdx == - 1 %7C%7C
  nums%5Ble
@@ -668,16 +668,17 @@
 ionIndex
+2
 (nums, t
@@ -690,17 +690,88 @@
 , false)
--
+;%0A%09%09// or targetRange%5B1%5D = extremeInsertionIndex(nums, target, false) - 
 1;%0A%0A%09%09re
@@ -1282,16 +1282,608 @@
 o;%0A  %7D%0A%0A
+  // Easier to understand, in my opinion.%0A  private static int extremeInsertionIndex2(int%5B%5D nums, int target, boolean left) %7B%0A      int lo = 0;%0A      int hi = nums.length;%0A      int ans = -1;%0A%0A      while (lo %3C= hi) %7B%0A        int mid = (lo + hi) / 2;%0A        if (nums%5Bmid%5D %3E target) %7B%0A          hi = mid - 1;%0A        %7D else if (nums%5Bmid%5D %3C target) %7B%0A          lo = mid + 1;%0A        %7D else %7B%0A          // nums%5Bmid%5D == target%0A          ans = mid;%0A          if (left) %7B%0A            hi = mid - 1;%0A          %7D else %7B%0A            lo = mid + 1;%0A          %7D%0A        %7D%0A      %7D%0A%0A      return ans;%0A  %7D%0A%0A
   public

add a easier solution