二分查找

定义

二分查找 [binary search]是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

适用:

一组由大到小或由小变大排列的数列,各数之间不要求连续.

过程:

如图,在进行查找前会对每个数字进行从0开始编号,编号和数字具有对应关系,对于要找的目标我们设为target,使用折半查询,若为小数则舍去小数部分.

如要查找23这个数字对应的编号为6,第一次折半结果为(0+9)/2 =4.5=4(设为中心点)<6

中心点不会参与计算,相邻的编号参与计算.

说明target在中心点右侧,则范围改为5-9.

二次折半:(5+9)/2 =7(中心点)>6

说明target在中心点左侧,则范围修改为5-6

三次折半:(5+6)/2 = 5.5 =5(中心点)<6

再往右移,只有编号6,即编号6对应的数字23是target