python 二分法查找思考理解小白向け

首先说一下二分法查找的思路。这是面向小白的课程,大佬请让步谢谢

给定一个有序的序列(必须是排好序的)例如[1,2,3,4,5,6,7,8,9,10,20,30,400],然后我们查询一个元素出现的坐标位置,默认是0开始。

比如我们查询20出现的位置。

首先,获取元素的总个数[1,2,3,4,5,6,7,8,9,10,20,30,400] ,13个元素,然后获取元素的首和尾的下标数 0和13

然后二分法查找,又叫折半查找,顾名思义就是一半一半的查找,那么我们就把上面的元素分成二份,如果出现小数则向下取整(math.foor的使用)(0+13)/2=6

所以我们确定了中间的坐标为6,好了 我们得到了两个区间[0,6] [7,13] 这是一个数组位置的区间,接下来我们就是分别来比较两个区间的。

首先比较左边部分。[01,2,3,4,5,6]=对应的元素是[1,2,3,4,5,6,7] 比较最大元素是否小于当前元素20 我们发现最大才7,7<20,所以我们舍弃这左边部分。

ok,下面就是右边部分了 [8,9,10,20,30,400],现在我们再对剩下的右半部分进行二分操作,得到二份数据[8,9,10]和[20,30,400]

同上操作舍弃左半部分继续操作右半部分,[20,30,400]得知 [20][30,40]好了 我们得到了最后的数字20.

比较的时候 

左边比较最大数小于指定数字,右边比较最小数大于指定数字 ,文字太罗嗦看不懂看图吧

原文地址:https://www.cnblogs.com/c-x-a/p/8916310.html