在数组中查找范围

Finding range in an array

本文关键字：范围 查找 数组      更新时间：2023-09-26

让我们假设我们有一个包含这些元素的数组(总是排序的)。

[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]

我们的目标是找到给定值的最小索引和最大索引，例如:假设我们正在搜索元素3的最小索引和最大索引。

我们很快看到，3的最小索引是8，最大索引是11。

对于值1，最小值为0，最大值为3。

你会如何开发一个解决方案，返回最小和最大的JavaScript?我试过这样做，但我不知道怎么做，我总是得到错误的答案。

您可以尝试Array.indexOf()和Array.lastIndexOf() 

var sortedArr =[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3];
console.log(sortedArr.indexOf(1));
console.log(sortedArr.lastIndexOf(1));

基本上Array.indexOf()和Array.lastIndexOf()会这样做，但它们会进行线性搜索(通过循环遍历整个数组直到找到元素)，这显然是在线性时间内完成的O(n)。

如果你的数组总是排序的，那么我们可以使用这个属性来优化它并使用二进制搜索。这是更快的方式，将在对数时间O(log n)。

之后，简单地检查查找到的索引之前(和之后)的元素，直到找到一个不等于元素的元素。

查找最后一次出现:

var i= foundIndex;
while(sortedArr[i] == sortedArr[foundIndex]){
    i++;
}
foundIndex = i;

第一次出现:

var i= foundIndex;
while(sortedArr[i] == sortedArr[foundIndex]){
    i--;
}
foundIndex = i;

就是这样!这将对运行时有很大帮助，特别是当您有大数组时。你可以在任何地方找到二进制搜索实现，只要使用它们中的任何一个。

这是你想要的吗?

var myarr = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3];
var minNum = myarr[0];
var maxNum = myarr[1];
var minNumStartINDX, maxNumStartINDX, minNumEndINDX, maxNumEndINDX;
/********************************************/
for (var x = 0; x < myarr.length; ++x) {
  if (minNum >= myarr[x]) {
    minNum = myarr[x];
    minNumEndINDX = x;
  }
}
for (var x = 0; x < myarr.length; ++x) {
  if (minNum >= myarr[x]) {
    minNumStartINDX = x;
    break;
  }
}
for (var x = 0; x < myarr.length; ++x) {
  if (maxNum <= myarr[x]) {
    maxNum = myarr[x];
    maxNumEndINDX = x;
  }
}
for (var x = 0; x < myarr.length; ++x) {
  if (maxNum <= myarr[x]) {
    maxNumStartINDX = x;
    break;
  }
}
/********************************************/
console.log(minNum);
console.log(minNumStartINDX + "-" + minNumEndINDX);
console.log(maxNum);
console.log(maxNumStartINDX + "-" + maxNumEndINDX);

var data={1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3};
var value=3;
var min=data.length;
var max=0;
for(var key in data){
   if(data[key]==value){
      if(key<min){
           min=key;
      }
   if(key > max){
          max=key;
     }
  }
console.log(min);
console.log(max);
相关文章：