折半查找技术也就是二分查找,通常称为二分法查找它的前期是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储、折半查找的基本思想是:
取中间记录作为比较对象若给定值与中间记录的关键字,则在中间记录的关键字相等则查找成功;若给定值小于中间记录的做半,去继续查找;若给定值大于中间记录的关键字则在中间记录的右半区继续查找。不断重复上述过程直到查找成功,或所有查找区域无记录查找失败为止。
在文本排重中需要用到折半查找需要查找一个数组中是否存在某个数。
算法维护着一个上边界hi下边界lo,使嘚要查找的值可能存在此之间例如,我们要查找88这个数:
下面图文示意查询88二分法的流程
首先我们对要查找的数据排好序然后用递归調用的方式实现折半查找,指定一个排好序的数组和要查找的值同时指定左边界和右边界
/*** 寻找排好数组中的一个值
*@paramleft 左边界,这个值必须位于数组长度区间内
*@paramright 右边界这个值必须位于数组长度区间内
*@return找到的值在数组中的位置,如果没找到就返回-1
用非递归的方法实现折半查找
需要注意的是:折半查询依赖于排好序的数组如果是一个没有排好序的数组,则不能使用折半查找首先需要排序处理。