BFE.devAI解答 - JavaScript 代码题
49. 含有重复元素的数组中返回特定元素的最后出现的位置

解法一：二分查找

由于数组已经排序，我们可以采用二分查找来快速定位特定元素的位置。但是由于可能存在重复元素，我们需要决定查找区间左右边界的位置。

具体来说，我们可以考虑寻找最后一个等于特定元素的位置，因此我们需要将右边界初始设置为数组长度减一。在二分查找中，我们需要按照以下步骤更新左右边界：

1. 如果中间元素等于目标元素，记录当前位置，并将左边界更新为中间位置加一，继续查找右侧区间；
2. 如果中间元素大于目标元素，说明目标元素可能出现在左侧区间，将右边界更新为中间位置减一；
3. 如果中间元素小于目标元素，说明目标元素可能出现在右侧区间，将左边界更新为中间位置加一。

当左右边界相遇时，如果之前出现过目标元素，返回最后出现的位置，否则返回 -1。

时间复杂度：$O(\log n)$，其中 $n$ 是数组长度。

空间复杂度：$O(1)$。

代码如下：

function lastIndexOf(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let lastIdx = -1; // 记录最后出现的位置
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
      lastIdx = mid;
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return lastIdx;
}

解法二：线性扫描

如果不使用二分查找，我们也可以考虑从前往后遍历整个数组，记录最后一个目标元素出现的位置。如果当前元素等于目标元素，就将最后出现位置更新为当前位置；如果当前元素大于目标元素，说明目标元素没有出现过，可以直接返回最后出现位置；如果遍历结束仍未找到目标元素，则返回 -1。

时间复杂度：$O(n)$，其中 $n$ 是数组长度。

空间复杂度：$O(1)$。

代码如下：

function lastIndexOf(arr, target) {
  let lastIdx = -1;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      lastIdx = i;
    } else if (arr[i] > target) {
      break;
    }
  }
  return lastIdx;
}