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

/*
Given an array of integers nums sorted in ascending order, find the starting 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
*/

//Solution
class Solution {
    public int[] searchRange(int[] arr, int target) {
        int[] retarray = {-1, -1};

        //check for first occurrence if target first
        int start = search(arr,target,true);
        int end = search(arr,target,false);

        retarray[0] = start;
        retarray[1] = end;
        return retarray;
    }
    
    int search(int[] arr, int target, boolean findStartIndex) {
        int ans = -1;
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            //int mid = (start + end)/2;  //might be possible the start + end exceeds the range of int
            //hence it may give to error
            //best way to code is
            int mid = start + (end - start) / 2;
            if (target < arr[mid]) {
                end = mid - 1;
            } else if (target > arr[mid]) {
                start = mid + 1;
            } else {
                //potential ans found
                ans = mid;
                if (findStartIndex) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return ans;
    }
}


//Another Solution:
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] arr = new int[2];
        arr[0] = startIndex(nums,target);
        arr[1] = endIndex(nums,target);
        return arr;
    }
    
    
    public int startIndex(int[] nums,int target){
        int start = 0;
        int ans = 0;
        boolean find = false;
        int end = nums.length - 1;
        while(start <= end){
            int mid = start + (end -start)/2;
            if(nums[mid] > target){
                end = mid-1;
            }else if(nums[mid] < target){
                start = mid+1;
            }else{
                ans = mid;
                find = true;
                end = mid-1;
            }
        }
        if(find){
            return ans;   
        }else{
            return -1;
        }
        
    }
  
    public int endIndex(int[] nums,int target){
        int start = 0;
        int ans = 0;
        boolean find = false;
        int end = nums.length - 1;
        while(start <= end){
            int mid = start + (end -start)/2;
            if(nums[mid] > target){
                end = mid - 1;
            }else if(nums[mid] < target){
                start = mid + 1;
            }else{
                ans = mid;
                find = true;
                start = mid + 1;
            }
        }
        if(find){
            return ans;   
        }else{
            return -1;
        }
    }
}