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)); // 5console.log(findNext(arr, 5)); // 7console.log(findNext(arr, 8)); // undefinedconsole.log(findNext(arr, 9)); // undefined

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

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