# Search for a Range

Given an array of integers`nums`sorted in ascending order, find the starting and ending position of a given`target`value.

Your algorithm's runtime complexity must be in the order o&#x66;_&#x4F;_(lo&#x67;_&#x6E;_).

If the target is not found in the array, return`[-1, -1]`.

**Example 1:**

```
Input:
 nums = [
5,7,7,8,8,10]
, target = 8

Output:
 [3,4]
```

**Example 2:**

```
Input:
 nums = [
5,7,7,8,8,10]
, target = 6

Output:
 [-1,-1]
```

## Analysis

寻找有重复的有序数列中的特定元素的下标范围，需要寻找左边界和右边界。这样单一的binary search会比较难实现，因此用两个binary search，一个找左边界，一个找右边界。

比较偏好Template #3，`left + 1 < right`作为循环条件，这样结尾的时候有两个备选，满足`left + 1 >= right`。

寻找左边界

```java
if (target <= nums[mid]) {
    right = mid;
} else {
    left = mid;
}
```

寻找右边界

```java
if (target >= nums[mid]) {
    left = mid;
} else {
    right = mid;
}
```

区别就在于`target == nums[mid]`时，是往右搜索（右边界）还是往左搜索（左边界）。

## Solution

**Using Template #3 - Two Binary Searches** (**6 ms, 33.53%)**

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        if (nums == null || nums.length == 0) return res;

        int left, right;

        // Binary Search 1 - Left Boundary        
        left = 0; 
        right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (nums[left] == target) {
            res[0] = left;
        } else if (nums[right] == target) {
            res[0] = right;
        }

        // Binary Search 2 - Right Boundary
        left = 0; 
        right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (target >= nums[mid]) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (nums[right] == target) {
            res[1] = right;
        } else if (nums[left] == target) {
            res[1] = left;
        }

        return res;
    }
}
```

Combined two binary searches In Helper function - (6ms 33.53%)

```java
class Solution {
    // returns leftmost (or rightmost) index in `nums` for `target` via binary search.
    private int extremeInsertionIndex(int[] nums, int target, boolean leftMost) {
        if (nums == null || nums.length == 0) return -1;
        int lo = 0;
        int hi = nums.length - 1;

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

    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};

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

        targetRange[0] = leftIdx;
        targetRange[1] = rightIdx;

        return targetRange;
    }
}
```
