BFE.devAI解答 - JavaScript 代码题
51. 含有重复元素的数组中返回特定元素的之后的元素

解题思路：

类似于二分查找，我们可以先找到特定数字的位置，然后再顺着数组往后查找第一个不等于它的数字。如果找到了这个数字，返回它的值；否则返回undefined。

具体实现：

function findNext(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  // 二分查找特定数字的位置
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      left = mid + 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // 如果找到了特定数字的位置，就顺着数组往后查找第一个不等于它的数字
  if (right >= 0 && right < arr.length && arr[right] === target) {
    while (right < arr.length && arr[right] === target) {
      right++;
    }
    return arr[right];
  } else {
    // 如果没找到特定数字，返回undefined
    return undefined;
  }
}

测试：

const arr = [1, 3, 3, 5, 5, 5, 7, 8, 8];
console.log(findNext(arr, 3)); // 5
console.log(findNext(arr, 5)); // 7
console.log(findNext(arr, 8)); // undefined
console.log(findNext(arr, 9)); // undefined

时间复杂度：$O(log_2 n)$

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