34.在排序数组中查找元素的第一个和最后一个位置 - Java 二分查找

原题地址：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

题解

实现一个二分查找，原则为：如果能找到这个元素则返回这个元素的最小下标，如果找不到则返回这个元素应当插入的下标

理所当然的，对于一段连续的target有

• 起始下标应为binSearch(nums,target)
• 结束下标应为binSearch(nums,target+1)-1

时间复杂度：O(logN)

空间复杂度：O(1)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans=new int[2];
        if(nums.length==0){
            ans[0]=-1;
            ans[1]=-1;
            return ans;
        }
        ans[0]=binSearch(nums,target,0,nums.length-1);
        if(ans[0]>=nums.length||ans[0]<0||nums[ans[0]]!=target){
            ans[0]=-1;
            ans[1]=-1;
            return ans;
        }
        else{
            ans[1]=binSearch(nums,target+1,0,nums.length-1)-1;
            return ans;
        }
    }

    int binSearch(int[] nums,int target,int begin,int end){
        if(end<begin)return begin;//找不到元素时返回begin
        else{
            int mid=(begin+end)/2;
            if(nums[mid]==target&&(mid==0||nums[mid-1]!=target))return mid;         //当且仅当mid为target且mid-1不为target时返回mid，考虑mid为0的特殊情况
            else if(nums[mid]>=target)return binSearch(nums,target,begin,mid-1);    //考虑到target ... mid ... target和larger ... mid ... larger的情况
            else return binSearch(nums,target,mid+1,end);
        }
    }
}