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

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

解题思路

两次二分，第一次专门找左边界，第二次专门找右边界；每次命中 target 时不直接返回，而是继续向目标边界方向收缩区间，直到循环结束，最后一次命中的位置就是边界

参考代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[] { solution(nums, target, true), solution(nums, target, false) };
    }

    private int solution(int[] nums, int target, boolean findLeft) {
        int left = 0;
        int right = nums.length - 1;
        int tmpIndex = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                tmpIndex = mid;
                if (findLeft) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return tmpIndex;
    }
}