查找第一个小于某个数的数

查找第一个小于某个数的数

数据模型如下：

xxxxxoooooozzzz 查找第一个大于 x 的 o，即查找x最后一次出现的位置

描述 给一个升序数组，找到 target 最后一次出现的位置，如果没出现过返回 -1

输入：nums = [1,2,2,4,5,5], target = 2
输出：2

输入：nums = [1,2,2,4,5,5], target = 6
输出：-1

我们使用前面 二分算法 描述过得算法思路，看看应该怎么更改（主要的改动点应该是在当 nums[middle] == target 的时候 left 或 right 应该继续移动） 我们看下第一个例子： [1, 2, 2, 2, 4, 5, 5] 假设当前的 middle = 1，指向第一个 2，我们看到最后一次出现 2 的位置在 middle 的右边，所以我们应该继续向 middle 的右边寻找，即::left = middle + 1::

public int findLastPositionOfTarget(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
           left = middle + 1;					 // 1.
           if (left == nums.length || nums[left] > target) {	   // 2.
	     return middle;
	   }								
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

1. left = middle ❌ 这种是错误的，会导致死循环，我们在二分算法那节中有讲到过：如果 left + 1 = right, 那么 middle = left + (left + 1 - left) / 2, middle 始终等于 left，导致死循环
2. 经过第一步后，left 指向了 middle 的下一个元素，
   1. 如果此时 left 恰好为数组的长度的值，则表示到了target 最后一次出现的位置是数组的末尾；case：nums: [1, 2, 2, 3, 5, 5, 5], target: 5
   2. 如果此时 left 指向的值大于 target 则表示当前的 middle 就是 target 最后一次出现的位置

---