lc-34

//Given an array of integers nums sorted in non-decreasing order, find the start
//ing and ending position of a given target value. 
//
// If target is not found in the array, return [-1, -1]. 
//
// You must write an algorithm with O(log n) runtime complexity. 
//
// 
// 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]
// Example 3: 
// Input: nums = [], target = 0
//Output: [-1,-1]
// 
// 
// Constraints: 
//
// 
// 0 <= nums.length <= 105 
// -109 <= nums[i] <= 109 
// nums is a non-decreasing array. 
// -109 <= target <= 109 
// 
// Related Topics Array Binary Search 
// 👍 11383 👎 306


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = searchRangeFunc(nums, target, true);
        result[1] = searchRangeFunc(nums, target, false);
        return result;
    }

    private int searchRangeFunc(int[] nums, int target, boolean left) {
        int from = 0, end = nums.length - 1;

        while (from <= end) {
            if (from == end) {
                if (nums[from] == target) {
                    return from;
                } else {
                    return -1;
                }
            }

            if (from + 1 == end) {
                if (nums[from] == target && nums[end] == target) {
                    if (left) {
                        return from;
                    } else {
                        return end;
                    }
                }

                if (nums[from] == target) {
                    return from;
                } else if (nums[end] == target) {
                    return end;
                } else {
                    return -1;
                }
            }

            int mid = from + (end - from) / 2;

            if (nums[mid] < target) {
                from = mid;
            } else if (nums[mid] > target) {
                end = mid;
            } else {
                if (left) {
                    end = mid;
                } else {
                    from = mid;
                }
            }
        }

        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)