道者编程


二分查找算法

二分查找法:又叫作折半查找法,它是在有序数组中查找指定数据的检索算法,比如一个数组(线性表)长度10万,查询某个数,二分查找首先把该线性表折半查询,找到这个中间位置对比看是不是,如果不是,再一次折半,重复搞下去,直到找到数据,每一次折半都踢出了一半的数据,不用一个一个对比找,所以查找效率相对高效。

两个条件:1:必须是线性表(数组),2:必须是有序存储。

算法:

left:数组开始位置;right:结束位置;mid:中间数(折半);

mid = (left+right)/2

if mid对应的val(mid相当于数组的key)大于 要查找的val:数据在前半段查找,left不变,right = mid - 1

if mid对应的val(mid相当于数组的key)小于  要查找的val:数据在后半段查找,right不变,left = mid +1

如果 == 那么就找到了该值!

如果 left 大于 right,说明数据不存在。(如果不满足上面两个条件,也可能出现这种情况,数据在,但是查不到。)

举例:

首先定义一个数组:$list,数组中有17个元素,我们找出元素:的位置

$list[1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71]
第一次:
left 0
right 16 
mid (0+16)/2 = 8(折半)
这里mid = 8,对应上面的list[mid] = 14 因为 14 > 7:所以在前半段查找,left不变,right = mid - 1

第二次:
left 0
right (mid -1 ) = 7
mid (0+7)/2 = 3 (折半)
这里mid = 3,对应上面的list[mid] = 6 因为 6<7:所以在后半段查找,right不变,left = mid + 1

第三次:
left (mid+1) = 4
right 7
mid (7+4)/2 = 5(折半)
这里mid = 5,对应上面的list[mid] = 8 因为 8 >7 所以在半段查找,left不变,right = mid -1

第四次:
left 4
right (mid -1) 4
mid (4+4)/2= 4 (折半)
这里mid = 4,对应上面的list[mid] = 7 ,终于找到了数据。

php:算法:

<?php
$list = [1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71];

echo binarySearch($list,7); //找7的位置

function binarySearch($list,$val){
	if(!is_array($list)){
		return "存储结构非数组";
	}
	$count = count($list);// 数组长度
	$left = 0; //数组开始位置
	$right = $count - 1; //数组结束位置,从0开始,故减1
	while($left <= $right){
		$mid = intval(($left+$right)/2);//获取中间数取整
		if ($list[$mid] == $val){ //找到了
			return '数组元素7的key是:'.$mid;//返回数组的位置(key)
		}
		if ($list[$mid] > $val){
			$right = $mid - 1;
		} else {
			$left = $mid +1;
		}
	}
	return "数据不存在";
}

输出:数组元素7的key是:4

go写法:

package main
import (
    "fmt"
)

func main() {
    list := []int{1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71}
    key := binarySearch(&list,7)
    fmt.Println(key) //-1表示不存在
}

func binarySearch(arr *[] int,val int)int{
    left , right := 0 , len(*arr) -1 //起始位置
    for left <= right {
        mid := (left + right) / 2 //中间数
        if left > right {
            return -1
        }

        if (*arr)[mid] == val { 
            return mid
        }

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


最新评论:
我要评论:

看不清楚


链接