javascript数据结构之二分查找简单介绍

快乐打工仔 分类:实例代码

查找数据可以使用两种方式,一种是顺序查找,一种是二分查找。

关于二分查找可以参阅javascript数据结构之顺序查找简单介绍一章节。

如果你要查找的数据是有序的,二分查找算法比顺序查找算法效率更高。

二分查找算法基本原理如下:

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 index = 1; index < list.length; index++) {
    if(list[index] < pivot) {
      left.push(list[index]);
    }else {
      right.push(list[index])
    }
  }
  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 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 index = 1; index < list.length; index++) {
    if(list[index] < pivot) {
      left.push(list[index]);
    }else {
      right.push(list[index])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 
 
// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var index = position -1; index > 0; --index) {
      if(arr[index] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var index = position + 1; index < arr.length; ++index) {
      if(arr[index] == 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);

运行结果图示如下:

前端教程

回复

我来回复
  • 暂无回复内容