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

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

Question:

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

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]

Thinking:

• Method:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null) return new int[]{-1, -1};
        int len = nums.length;
        int index = binarySearch(0, len - 1, nums, target);
        if(-1 == index) return new int[]{-1, -1};
        else{
            int high = index;
            while(++high < len && nums[high] == target){};
            int low = index;
            while(--low >= 0 && nums[low] == target){}
            return new int[]{low + 1, high - 1};
        }
    }
    private static int binarySearch(int low, int high, int[] nums, int target){
        if(low > high)
            return -1;
        int mid = low + (high - low) / 2;
        int midVal = nums[mid];
        if(midVal == target) return mid;
        if(midVal > target)
            return binarySearch(low, mid - 1, nums, target);
        else
            return binarySearch(mid + 1, high, nums, target);
    }
}

二刷

先通过二分法查找出target的一个位置，再通过左右延伸找出开头和结尾的位置。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0) return new int[]{-1, -1};
        int res = binarySearch(nums, target, 0, nums.length - 1);
        if(res == -1) return new int[]{-1, -1};
        int low = res, high = res;
        while(low >= 0 && nums[low] == target){low --;}
        while(high < nums.length && nums[high] == target){high ++;}
        return new int[]{low + 1, high - 1};
    }
    private int binarySearch(int[] nums, int target, int low, int high){
        if(low > high || low < 0 || high >= nums.length) return -1;
        int mid = low + (high - low) / 2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] > target)
            return binarySearch(nums, target, low, mid - 1);
        else
            return binarySearch(nums, target, mid + 1, high);
    }
}

###Third Time

• Method 1: Binary Search

   class Solution {
   	public int[] searchRange(int[] nums, int target) {
   		if(nums == null || nums.length == 0) return new int[]{-1, -1};
   		int index = bs(nums, 0, nums.length - 1, target);
   		if(index == -1) return new int[]{-1, -1};
   		int left = index, right = index;
   		while(--left >= 0 && nums[left] == target){}
   		while(++right < nums.length && nums[right] == target){}
   		return new int[]{left + 1, right - 1};
   	}
   	private int bs(int[] nums, int low, int high, int target){
   		if(low > high) return -1;
   		int mid = low + (high - low) / 2;
   		if(nums[mid] == target) return mid;
   		else if(nums[mid] < target) return bs(nums, mid + 1, high, target);
   		else return bs(nums, low, mid - 1, target);
   	}
   }