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

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

        // find the index of the leftmost appearance of `target`.
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                res[0] = i;
                break;
            }
        }

        // if the last loop did not find any index, then there is no valid range
        // and we return [-1, -1].
        if (res[0] == -1) {
            return res;
        }

        // find the index of the rightmost appearance of `target` (by reverse
        // iteration). it is guaranteed to appear.
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] == target) {
                res[1] = j;
                break;
            }
        }

        return res;
    }
}

class Solution {
    private int findLeft(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        // search range: [0, nums.length - 1]
        int left = 0;
        int right = nums.length - 1;
        // end the loop when left == right + 1
        while (left <= right) {
            // avoid integer overflow
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // shrink the right bound to find the left
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        // if the target is larger than all the number (left == nums.length) 
        // returns -1
        if (left <= nums.length - 1 && nums[left] == target) {
            return left;
        } else {
            return -1;
        }
    }

    private int findRight(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        // search range: [0, nums.length - 1]
        int left = 0;
        int right = nums.length - 1;
        // end the loop when left == right + 1
        while (left <= right) {
            // avoid integer overflow
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // shrink the left bound to find the right
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        // if the target is smaller than all the number (right == -1) 
        // returns -1
        if (right >= 0 && nums[right] == target) {
            return right;
        } else {
            return -1;
        }
    }

    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeft(nums, target), findRight(nums, target)};
    }
}