php 二分发查找，golang二分法查找

待我称王封你为后i 2022-11-01 05:56 145阅读 0赞

### 要实现二分法查找数据，首先要明白什么是二分法 ###

**1.首先这个数据必须是有序的，如果这个数组不是有序的，不用排了，根本不符合算法的要求**

**2.二分法关键地方是中间数的查找，中间数的坐标 = (最左侧数的坐标+最右侧数的坐标) / 2然后取整，中间数在每次查找都会变化**

### 请看详细解析，认真看完就明白了什么是二分法查找了 ###

现在有数组：10,14,21,38,45,47,53,81,87,99，查找47这个数

第一次查找：数组最左侧的坐标是0，最右侧的坐标是数组的(长度-1)=9 ，因为数组是从0开始的

中间数的位置 = (0+9)/2 然后取整 = 4，则坐标为4的数据的值是45，判断45是否等于47，如果等于,则查找第一次就找到了

如果小于47，则说明中间值左边的数据都小于47，不用看左边的数了，查右边的就行了，现在的最左边的坐标 = 中间数坐标+1=4+1=5，现在的中间数坐标是5，最右边的坐标不变9

第二次查找：剩余的47,53,81,87,99在这些数据中再找出中间值，上一步确定了现在最左边的坐标是5，最右边的坐标是9，则中间数的坐标 = (5+9)/2然后取整 = 7，值是81

数组：10,14,21,38,45,47,53,81,87,99第7位的数值是：81，判断81是否等于47，不等于，81大于47，则81和81右侧的数不用看了，中间数的值大于查找的目标数，则目标数在中间数的左侧，

可以扔掉中间数后面的数，剩余47,53，现在最右侧的坐标 = 中间数的坐标 - 1 = 7-1 = 6，最左侧的坐标不变 = 5，中间数的坐标 = （5+6）/2取整 = 5，中间数的值=47

第三次查找：剩余47,53这两个数，第二次查找到的中间数的值是47,判断47是否等于查找的数47，结果是相等的，所以就找到了目标数所在的位置就是坐标5

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyNzE5NA_size_16_color_FFFFFF_t_70]

看完上面的二分法解析，下面这堆数，用二分查找法去查，相信各位老爷们都知道怎么做了

### **数组：11,22,33,44,55,66,77,88,99 使用二分法查找44，这个数组有9个元素** ###

第1次查找的中间数是：55，55大于44，则看中间数55左侧的数即可
    
    第2次查找的中间数是：22，22小于44，则看中间数22右侧的数即可
    
    第3次查找的中间数是：33，33小于44，则看中间数33右侧的数即可
    
    第4次查找的中间数是：44，中间数是44，中间数等于查找的数，则查找到结果
    
    查找到第4次找到结果44,所在坐标是3

**PHP版本二分法查找**

<?php
    //二分法查找90,二分查找法元素必须是升序的排列方式,如果不是升序的则,必须先排序
    $arr = array(10,20,30,40,50,60,70,80,90);
    $num = 90;
    
    function erfenSearch($findNum,$arr){
        $searchCount = 0;
        $arrayCount = count($arr);
        $middleMumPos = round($arrayCount/2)-1;//中间数
    
        $left = 0 ;
        $right = $arrayCount-1;//8
    
        for($i=0;$i<$arrayCount;$i++){
            $middleNum = $arr[$middleMumPos];//中间数
            $searchCount++;
    
            echo PHP_EOL."第{$searchCount}次查找的中间数是：".$middleNum.PHP_EOL;
    
            if($middleNum==$findNum){
                $res =  "查找到第{$searchCount}次找到结果{$findNum},所在坐标是{$middleMumPos}";
                return $res;
            }elseif ($middleNum>$findNum){
                //中间数大于查找的数,则右侧的可以扔掉了
                $right = $middleMumPos-1;
                $middleMumPos = intval(($right+$left)/2);
            }elseif($middleNum<$findNum){
                //中间数小于查找的数,左侧的可以扔掉了
                $left = $middleMumPos+1;
                $middleMumPos = intval(($right+$left)/2);
            }
        }
    
        return "查找次数{$searchCount}次,没有找到结果";
    }
    
    $result = erfenSearch($num,$arr);
    var_dump($result);

运行结果：

第1次查找的中间数是：50

第2次查找的中间数是：70

第3次查找的中间数是：80

第4次查找的中间数是：90  
string(47) "查找到第4次找到结果90,所在坐标是8"

**golang版本,二分法查找**

package main
    
    import (
    	"fmt"
    	"math"
    )
    
    func main() {
    	var array = []int{10,20,30,40,50,60,70,80,90,100}
    	fmt.Println(array)
    
    	pos,err := erfenSearch(40,array)
    	fmt.Println("查找到数据坐标是:",pos,err)
    }
    
    //二分法查找
    func erfenSearch(findNum int,arraySource []int)(pos int,msg string){
    	arrayCount := len(arraySource)//总长度
    	var searchNum int
    	var left float64 = 0
    	var right float64 = float64(arrayCount)-1
    
    	middlePos := math.Floor(right-left)/2//中间数位置
    
    	for i:=1;i<=arrayCount;i++{
    
    		middleNum := arraySource[int(middlePos)]//中间数的值
    		searchNum++
    		fmt.Println("检索次数：",searchNum,"中间数:",middleNum)
    		if middleNum==findNum{
    			return int(middlePos),""//找到结果返回
    		}else if middleNum>findNum{
    			right = middlePos-1
    		}else if middleNum<findNum{
    			//中间数小于查找的数,左侧的可以扔掉了
    		    left = middlePos+1
    		}
    		middlePos = math.Floor((right+left)/2)
    	}
    	return pos,"没有找到结果"
    }

运行过程：\[10 20 30 40 50 60 70 80 90 100\]  
检索次数： 1 中间数: 50  
检索次数： 2 中间数: 20  
检索次数： 3 中间数: 30  
检索次数： 4 中间数: 40  
查找到数据坐标是: 3

文章参考，太多了，写完后都不知道是抄谁的，golang和php版本是我写的，文字也是我写的，图是抄人家的(懒得画图)，...

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyNzE5NA_size_16_color_FFFFFF_t_70]: /images/20221024/fa451450fe8b43ab85cc0823c85bf5e4.png