数据结构与算法 - 检索算法

在列表中查找数据有两种方式：顺序查找 和 二分查找。
顺序查找适用于元素随机排列的列表；
二分查找适用于元素已排序的列表；（二分查找效率更高，但是查找之前需要额外的时间对列表中的元素排序）

【一】 顺序查找(又称为线性查找)

从第一个元素开始查找，循环列表，逐个对比查找

function seqSearch(arr, data) {
   for (var i = 0; i < arr.length; ++i) {
      if (arr[i] == data) {
         return true;
      }
   }
   return false;
}

<!-- 返回索引 -->
function seqSearch(arr, data) {
   for (var i = 0; i < arr.length; ++i) {
      if (arr[i] == data) {
         return i;
      }
   }
   return -1;
}

需要注意的是这种方式，比内置的Array.indexof()方法慢。

1.查找最大值和最小值

function findMin(arr) {
   var min = arr[0];
   for (var i = 1; i < arr.length; ++i) {
      if (arr[i] < min) {
         min = arr[i];
      }
   }
   return min;
}

2.使用自组织数据

对数据的查找遵循“80-20原则”。
[80-20原则：指对某一数据集执行的80%的查找操作都是对其中20%的数据元素进行查找。自组织的方式会把这20%的数据置于数据集的起始位置，这样便可以通过一个简单的顺序查找快速找到他们]；
其实，类似这种“80-20原则”的概率分布被称为帕累托（Pareto）分布，他是有帕累托(Vilfredo Pareto)在19世纪末期研究收入和财富的分布时发现的。

下面对正常的顺序查找加入自组织方式

function seqSearch(arr, data) {
   for (var i = 0; i < arr.length; ++i) {
      if (arr[i] == data) {
         if (i > 0) {
            <!-- swap(arr,i,i-1); -->
            arr.swap(i,i-1);
         }
         return true;
      }
   }
   return false;
}

swap() 方法是对数组的数据进行调换的方法；

Array.prototype.swap = function(index1, index2) {
    let temp = this[index1];
    this[index1] = this[index2];
    this[index2] = temp;
    return this;
}

另外一种添加自组织数据的方法： 将找到的数据移动到数据集的其实位置，但是如果这个元素已经接近其实位置，则不会对它进行交换。我们只对距离数据集起始位置一定范围外的元素进行交换。我们只需要定义哪些是离数据集起始位置足够近的元素。再次参照“80-20原则”，我们确定原则：
仅当数据位于数据集的前20%元素之外时，该数据才需要被重新移动到数据集的起始位置。

function seqSearch(arr, data) {
   for (var i = 0; i < arr.length; ++i) {
      if (arr[i] == data && i > (arr.length * 0.2)) {
         swap(arr,i,0);
         return true;
      }
      else if (arr[i] == data) {
         return true;
      }
   }
   return false;
}

【二】 二分查找算法

如果要查找的数据是有序的，二分查找算法比顺序查找算法更高效。
举个简单的例子，我买了件衣服，朋友觉得不错，想知道衣服的价格，让朋友来猜衣服的价格。我告诉他结果，无非就三种情况出现，直接猜对了，猜大了，猜小了；将这个策略实现为二分查找算法，不过，这个算法只对有序的数据集有效。

算法描述如下：
(1)将数组的第一个位置设为下边界
(2)将数组的最后一个元素所在的位置设置为上边界(数组的长度减一)
(3)若下边界等于或小于上边界，做如下操作
a.将中点位置设置为(上边界加下边界)除以2
b.如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1
c.如果中点的元素大于查询的值，则将上边界设置为中点元素所在下边减1
d.否则中点元素即为要查找的数据，可以进行返回

function binSearch(arr, data) {
   var upperBound = arr.length-1;
   var lowerBound = 0;
   while (lowerBound <= upperBound) {
      var mid = Math.floor((upperBound + lowerBound) / 2);
      if (arr[mid] < data) {
         lowerBound = mid + 1;
      }
      else if (arr[mid] > data) {
         upperBound = mid - 1;
      }
      else {
         return mid;
      }
   }
   return -1;
}

var nums = [];
for (var i = 0; i < 100; ++i) {
   nums[i] = Math.floor(Math.random() * 101);
}
insertionsort(nums);
dispArr(nums);
print();
putstr("Enter a value to search for: ");
var val = parseInt(readline());
var retVal = binSearch(nums, val);
if (retVal >= 0) {
   print("Found " + val + " at position " + retVal);
}
else {
   print(val + " is not in array.");
}

计算重复次数(在二分查找的基础上，向上和向下查找相同的值)

function count(arr, data) {
   var count = 0;
   var position = binSearch(arr, data);
   if (position > -1) {
      ++count;
      for (var i = position-1; i > 0; --i) {
         if (arr[i] == data) {
            ++count;
         }
         else {
            break;
         }
      }
      for (var i = position+1; i < arr.length; ++i) {
         if (arr[i] == data) {
            ++count;
         }
         else {
            break;
         }
      }
   }
   return count;
}

【三】 查找文本数据

function binSearch(arr, data) {
   var upperBound = arr.length-1;
   var lowerBound = 0;
   while (lowerBound <= upperBound) {
      var mid = Math.floor((upperBound + lowerBound) / 2);
      if (arr[mid] < data) {
         lowerBound = mid + 1;
      }
      else if (arr[mid] > data) {
         upperBound = mid - 1;
      }
      else {
         return mid;
      }
   }
   return -1;
}

function insertionsort(arr) {
   var temp, inner;
   for (var outer = 1; outer <= arr.length-1; ++outer) {
      temp = arr[outer];
      inner = outer;
      while (inner > 0 && (arr[inner-1] >= temp)) {
         arr[inner] = arr[inner-1];
         --inner;
      }
      arr[inner] = temp;
   }
}

var words = read("words.txt").split(" ");
insertionsort(words);
var word = "rhetoric";
var start = new Date().getTime();
var position = binSearch(words, word);
var stop = new Date().getTime();
var elapsed = stop - start;
if (position >= 0) {
   print("Found " + word + " at position " + position + ".");
   print("Binary search took " + elapsed + " milliseconds.");
}
else {
   print(word + " is not in the file.");
}

文章结尾总结：在这个高速处理器的时代，除非面向大数据集，否则要测量顺序查找和二分查找耗时上的区别变得越来越困难。
然而，处理大数据集时二分查找要比顺序查找速度快，这一观点在数学理论上已经得到证明。在决定算法性能的每一步循环嵌套中，二分查找减少了一半的查找量。