javascript检索算法代码举例

今天看到一篇谈javascript的文章.引起我的好奇.主要讲查找数据有2种方式，顺序查找和二分查找。顺序查找适用于元素随机排列的列表。二分查找适用于元素已排序的列表。二分查找效率更高，但是必须是已经排好序的列表元素集合.

在多是泛泛之谈的今天.有这个javascript的文章实属难得.在这篇CODEGO.NET的javascript文章里面谈的主要是检索算法.包括数据结构与算法的一些演示.

个人觉得挺有用.所以不敢独享就发出来.加上我自己的一些经验之谈了.

一：顺序查找

顺序查找是从列表的第一个元素开始对列表元素逐个进行判断，直到找到了想要的结果，或者直到列表的结尾都没有找到想要找的元素。

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

我们也可以返回匹配元素位置的顺序查找函数

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

二：查找最小值和最大值

在数组中查找最小值算法如下：

   1. 将数组第一个元素赋值给一个变量，把这个变量作为最小值。

   2. 开始遍历数组，从第二个元素依次同当前最小值进行比较。

   3. 如果当前元素的数值小于当前最小值，则将当前元素设为新的最小值。

   4. 移动到下一个元素，重复步骤3.

   5.  当程序结束时，这个变量中存储的就是最小值。

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

查找最大值算法和上面最小值类似，先将数组中第一个元素设为最大值，然后循环对数组剩余的每个元素与当前最大值进行比较，如果当前元素的值大于当前的最大值，则将该元素的值赋值给最大值。代码如下：

?123456789 function findMax(arr) {   var max = arr[0];   for(var i = 1; i < arr.length; ++i) {     if(arr[i] > max) {       max = arr[i];     }   }   return max;  } 

三：二分查找法。

 如果你要查找的数据是有序的，二分查找算法比顺序查找算法效率更高。二分查找算法基本原理如下：

 1. 将数组的第一个位置设置为下边界(0).

 2. 将数组的最后一个元素所在的位置设置为上边界(数组的长度减1)。

 3. 若下边界等于或小于上边界，则做如下操作：

    A. 将中点设置为(上边界加上下边界) 除以2.

    B. 如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1.

    C. 如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减1.

    D. 否则中点元素即为要查找 的数据，可以进行返回。

// 二分查找算法 function binSearch(data,arr) { var lowerBound = 0;   var upperBound = arr.length - 1;   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 qSort(list) {   if(list.length == 0) {     return [];   }   // 存储小于基准值的值   var left = [];   // 存储大于基准值的值   var right = [];   var pivot = list[0];   for(var i = 1; i < list.length; i++) {     if(list[i] < pivot) {       left.push(list[i]);     }else {       right.push(list[i])     }   }   return qSort(left).concat(pivot,qSort(right)); }  // 测试代码 var numbers = [0,9,1,8,7,6,2,3,5,4]; var list = qSort(numbers); console.log(binSearch(6,list)); 

四：计算重复次数；

当二分查找算法binSearch()函数找到某个值时，如果在数据集中还有其他相同的值出现，那么该函数会定位在类似值附近，换句话说，其他相同的值可能会出现已找到值的左边或者右边。

那么我们最简单的方案是写2个循环，一个同时对数据集向下遍历或者向左遍历，统计重复次数；然后，向上或向右遍历，统计重复次数。代码如下：

// 计算重复次数 function count(data,arr) {   var count = 0;   var arrs = [];   var position = binSearch(data,arr);   if(position > -1) {     ++count;     arrs.push({"index":count});     for(var i = position -1; i > 0; --i) {       if(arr[i] == data) {         ++count;         arrs.push({"index":count});       }else {         break;       }     }     for(var i = position + 1; i < arr.length; ++i) {       if(arr[i] == data) {         ++count;         arrs.push({"index":count});       }else {         break;       }     }   }   return arrs; }  // 测试重复次数的代码 var arr = [0,1,1,1,2,3,4,5,6,7,8,9]; var arrs = count(1,arr); console.log(arrs); console.log(arrs.length); 

本文出自 “zhentanxiaoxiao” 博客，请务必保留此出处http://9888127.blog.51cto.com/9878127/1628187