34. Find First and Last Position of Element in Sorted Array

time: O(logn)

space: O(1)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[]{-1, -1};
        if (nums == null || nums.length == 0) return res;
        
        int first = findFirst(nums, target);
        
        if (first == -1) return res;
        
        res[0] = first;
        res[1] = findLast(nums, target);
        return res;
    }
    private int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1; // or left + (right - left)/2
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] != target ? -1 : left;
    }
    private int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1)/2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

Latest version

time: O(logn)

space: O(1)

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[] {findFirst(nums, target), findLast(nums, target)};
    }
    public int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid - 1; // when find, keep to find left
            }
        }
        if (left == nums.length) {
            return -1;
        }
        return nums[left] == target ? left : -1;
    }
    public int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                left = mid + 1; // when find, keep to find right
            }
        }
        if (left - 1 < 0) {
            return -1;
        }
        return nums[left - 1] == target ? left - 1 : -1;
    }
}
```

best solution!!

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeftBound(nums, target), findRightBound(nums, target)};
    }
    public int findLeftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        int leftBound = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                leftBound = Math.min(leftBound, mid);
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return leftBound == Integer.MAX_VALUE ? -1 : leftBound;
    }
    public int findRightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        int rightBound = Integer.MIN_VALUE;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                rightBound = Math.max(rightBound, mid);
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return rightBound == Integer.MIN_VALUE ? -1 : rightBound;
    }
}
```

Best and make sense Solution

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeftMost(nums, target), findRightMost(nums, target)};
        
    }
    //[5,7,7x,8,8x,10]
    private int findLeftMost(int[] nums, int target) {
        int left = 0; //3
        int right = nums.length-1; //5
        
        while (left <= right) {
            int mid = left + (right - left)/2; // 3 + (5-3)/2 = 4
            if (nums[mid] == target) {
                if (mid-1 >= 0 && nums[mid-1] == target) {
                    right = mid - 1; // 左邊還有一樣的, 往左找
                } else {
                    return mid;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    private int findRightMost(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        
        while (left <= right) {
            int mid = left + (right - left)/2; // 1
            if (nums[mid] == target) {
                if (mid+1 < nums.length && nums[mid+1] == target) {
                    left = mid + 1; // 右邊還有一樣的, 往右找
                } else {
                    return mid;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
```