LeetCode34. Find First and Last

题目---二分题

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]

题目的大意是给定一个有序数组和一个目标数，求此目标数在数组中的起始位置。
代码贴上：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0)
            return new int[]{-1,-1};
        int start = searchBoundary(nums,target);
        int end = searchBoundary(nums,target+1);
        //target不存在
        if(nums[start]!=target)
            return new int[]{-1,-1};
        if(nums[end]!=target)
            end = end-1;
        return new int[]{start,end};
    }
    
    //使用二分求开始位
    public int searchBoundary(int[] nums,int target){
        int lo = 0;
        int hi = nums.length-1;
        while(lo<hi){
            int mid = (lo+hi)/2;
    //如何控制停留再开始位的边界判断
            if(nums[mid]<target)
                lo = mid +1;
            else
                hi = mid;
        }
        return hi;
    }
}

此题一看就想到应该用二分的思想，设计二分算法去求得一个数在数组中的起始,,可分两步走：

• 求的开始位置
  可将二分的停止位置设计在开始的位置，只需将二分的高位hi在target<=nums[mid]时移动到mid为即可。这样可以保证二分结束时高位hi一定处于target的开始位。

• 求结束位置
  求target的结束位置需要点技巧，我可以转换为求开始位置。怎么转换？我们只需去求target+1的开始位即可，无论target+1是否存在。例如[1,2,2,3,3,4],我们要求2的结束位只需求得3的开始位再减1即可。但是可能出现这种情况[1,2,2],这样去求3的开始位将停留在最后一位，此时不需要减一，因此要做个判断此位是否已等于target再决定是否减一。