经典排序之折半查找

腿子代码了

发布于 2023-10-08 10:42:01

3380

发布于 2023-10-08 10:42:01

排序含义

了解一个知识，必须先要从其含义开始。折半查找，又称二分法查找。意在一个有序的序列当中，从最大值与最小值开始，从两个值的中间值为分渠道，再次判断是否位于区间内，重复获取中间值，直至找到需要查找的值。折半查找，适用于数据量很大的情况。具体是什么意思呢，一个例子搞定：数字炸弹游戏

一个1-100的数字，其中有一个数字是炸弹，每次猜一个数，怎么样才能猜出最快呢。排除运气成分，用二分法可以最快猜出这个数字炸弹。利用二分法为大家演示。假如炸弹是28

在1-100，中，首先猜50，错误。区间来到【1-50】，再次猜数字25，区间来到【26-49】。回答错误，再一次猜数字等等等，直到猜出数字28。这就是二分法中次数最长的一种。

直到此，大概对与折半查找有这一定的理解了。

排序图例

选择一个1-100的有序区间（数字炸弹为28）一定是要有序的区间

第一次查找猜数字50 区域变为

第二次查找猜数字25

区域变为

以此往下，第n次查找到数字找到数字炸弹28；

代码实现

定义一个数组必须是有序数组，必须是有序数组，必须是有序数组，重要的事情说三遍！！！

var arr=[6,10,12,23,43,52,58,68,70,94,128]

定义一个方法封装查找功能参数一:查找的值。参数二：有序的数组

/*
param{
key:待查找的值
arr:待查找的数组
}
*/
var mysearch=function(key,arr){
    var left=0;
    var right=arr.length-1;
    while(left <= right){
        let mid=Math.floor((right-left)/2) +left;
        if(arr[mid]==key){
            return mid+1;
        }else if( arr[mid]>key){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return -1
   }

代码解析

首先，需要定义两个变量，负责定义两个边界值，因为在数组当中都是以下标作为确定值的方式之一。所以将第一个值定义为零，第二个值定义为数组的长度-1

	var left=0;
    var right=arr.length-1;

定义一个循环，负责每次二分（折半）查找。循环的条件为右边的边界值大于等于左边的边界值，也可以左边大于等于右边，具体随自己而定。

 while(left <= right){
      //方法体
    }

现在定义方法循环体的内容。定义一个中间值，作为每次折中查找的中间值。采用right-left而不是相加的原因是避免数据溢出。

  let mid=Math.floor((right-left)/2) +left;

添加判断判断一：当中间值等于key的值，说明中间值等于数字炸弹，猜想成功，结束，返回该值在数组中的第几个（并不是下标，具体由要求灵活改变）。判断二：当中间值比key值大时，则说明key值位于最小值与中间值之间，那么就可以将右侧的最大临界值改变为这个中间值。判断三：当中间值比key值小时，则说明key值位于最大值与中间值之间，那么就可以将左侧的最小临界值改变为这个中间值。

        if(arr[mid]==key){
            return mid+1;
        }else if( arr[mid]>key){
            right=mid-1;
        }else{
            left=mid+1;
        }

最后，如果仍没查找到这个值，则说明值不存在与这个数组或序列当中，则返回-1提示查无此数。