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

Problem

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

1. 题目简述

给出一个有序数组和一个target，找到其上下边界。例如：

Example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

2. 算法思路

二分查找的模板题目，背背背！！！！

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int[] res = new int[2];
        
        while (l < r) {
            int mid = l + r >> 1;
            // 希望取左边界
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        
        if (nums.length == 0 || nums[l] != target) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        
        res[0] = l;
        
        l = 0;
        r = nums.length - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        res[1] = l;
        
        return res;
    }
}