# Search for a Range
###### tags: `Medium`
>question : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/

>reference : [Binary Search](https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1)

>related problem :
## My Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) {
            int[] ans = {-1,-1};
            return ans;
        }
        int l = 0;
        int r = nums.length - 1;
        int index = 0;
        while(l <= r) {
            // avoid integer overflow
            // int mid = (l + r) / 2;
            int mid = l + (r - l) / 2;
            if(nums[mid] > target)
                r = mid - 1;
            else if(nums[mid] < target)
                l = mid + 1;
            else {
                index = mid;
                break;
            }
        }
        
        if(nums.length == 0 || nums[index] != target) {
            int[] ans = {-1,-1};
            return ans;
        }
        
        l = index;
        r = index;
        while(l - 1 >= 0 && nums[l - 1] == target)
            l--;
        while(r + 1 < nums.length && nums[r + 1] == target)
            r++;
        int[] ans = {l, r};
        return ans;
    }
}

## Other Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int[] result = new int[2];
        result[0] = findFirst(nums,target);
        result[1] = findLast(nums,target);
        return result;
        
    }
    
    public int findFirst(int[] nums, int target){
        
        int result = -1;
        int low = 0;
        int high = nums.length - 1;

        while(low <= high){
            int mid = low + ((high-low)/2);

            if (nums[mid] < target){
                low = mid +1;
            } else if (nums[mid] > target){
                high = mid - 1;
            } else { // nums[mid] == target
                result = mid;
                // Because nothing after mid
                // can be the first occurance of target.
                // Maybe mid is the first occurance, maybe not.
                // So let's narrow the target for [0...mid-1] and find out
                high = mid - 1; 
            }
        }
        return result;  
    }
    
        public int findLast(int[] nums, int target){
        
        int result = -1;
        int low = 0;
        int high = nums.length - 1;
        
        while(low <= high){
            
            int mid = low + (high-low)/2;
            
            if (nums[mid] < target){
                low = mid +1;
            } else if (nums[mid] > target){
                high = mid - 1;
            } else { // nums[mid] == target
                result = mid;
                // because nothing before mid
                // can be the last occurance of target.
                // maybe mid is the last occurance , maybe not
                // so let's narrow the target for [mid+1...high] and find out
                low = mid + 1;
   
            }
        }

        return result;
    }
}