LeetCode: 34. Find First and Last Position of Element in Sorted Array 有序数组的第一个或者最后一个出现的目标数二分查找

矫情吗；* 2021-06-24 16:11 269阅读 0赞

**试题**  
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\]

**代码**

两个二分查找算法分开写，注意两个mid值算法（一个加1，一个没有）是不同的，主要是为了能够到达终止循环条件。  
另外最后要对left的位置及值进行判断。

class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums==null || nums.length==0) return new int[]{-1,-1};
            int first = searchFirst(nums, target);
            int end = searchEnd(nums,target);
            return new int[]{first, end};
        }
        
        public int searchFirst(int[] nums, int target){
            int left=0, right=nums.length-1;
            while(left<right){
                int mid = left+(right-left)/2;
                if(nums[mid]==target){
                    right = mid;
                }else if(nums[mid]<target){
                    left = mid+1;
                }else if(nums[mid]>target){
                    right = mid-1;
                }
            }
            if(left>=0 && left<nums.length && nums[left]==target)   //或者if(nums[left]==target)
                return left;
            else
                return -1;
        }
        
        public int searchEnd(int[] nums, int target){
            int left=0, right=nums.length-1;
            while(left<right){
                int mid = left+(right-left+1)/2;
                if(nums[mid]==target){
                    left = mid;
                }else if(nums[mid]<target){
                    left = mid+1;
                }else if(nums[mid]>target){
                    right = mid-1;
                }
            }
            if(left>=0 && left<nums.length && nums[left]==target)  //必须判断left范围，输入[2,2] 3会导致left超出范围。或者使用if(nums[right]==target) return right
                return left; 
            else
                return -1;
        }
    }

**官网代码：**

class Solution {
        // returns leftmost (or rightmost) index at which `target` should be
        // inserted in sorted array `nums` via binary search.
        private int extremeInsertionIndex(int[] nums, int target, boolean left) {
            int lo = 0;
            int hi = nums.length;
    
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (nums[mid] > target || (left && target == nums[mid])) {
                    hi = mid;
                }
                else {
                    lo = mid+1;
                }
            }
    
            return lo;
        }
    
        public int[] searchRange(int[] nums, int target) {
            int[] targetRange = {-1, -1};
    
            int leftIdx = extremeInsertionIndex(nums, target, true);
    
            // assert that `leftIdx` is within the array bounds and that `target`
            // is actually in `nums`.
            if (leftIdx == nums.length || nums[leftIdx] != target) {
                return targetRange;
            }
    
            targetRange[0] = leftIdx;
            targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
    
            return targetRange;
        }
    }