JavaScript程序，用于在两个排序的数组中查找公共元素

我们需要编写一个JavaScript函数，该函数接受两个已排序的数组（均以相同顺序排序）。该函数应准备并返回第三个数组，该数组包含两个元素都通用的所有元素。

我们可以通过在O（m * n）时间（m和n是数组的各自长度）中甚至在O（m + n）中使用两个循环来轻松解决此问题。

但是，由于对数组进行了排序，我们可以通过迭代较小的数组并使用二进制搜索算法在较大的数组中搜索元素来节省时间。

这样，函数的时间复杂度将降低到O（n * logm）（m> n），远好于O（m + n），特别是在m >> n的情况下

示例

为此的代码将是-

const arr1 = [2, 5, 7, 8, 9, 11, 14];
const arr2 = [1, 3, 4, 5, 6, 8, 11, 16];
const binarySearch = (target, arr = []) => {
   let first = 0;
   let last = arr.length − 1;
   let position = −1;
   let found = false;
   let middle;
   while (found === false && first <= last) {
      middle = Math.floor((first + last)/2);
      if (arr[middle] == target) {
         found = true;
         position = middle;
      } else if (arr[middle] > target) {
         last = middle − 1;
      } else {
         first = middle + 1;
      }
   }
   return position;
}
const findCommon = (arr1 = [], arr2 = []) => {
   const res = [];
   for (let i = 0; i < arr1.length; ++i){
      if (binarySearch(arr1[i], arr2) !== −1){
         res.push(arr1[i]);
      };
   };
   return res;
};
console.log(findCommon(arr1, arr2));

输出结果

控制台中的输出将是-

[5, 8, 11]