简介:二分查找法,也叫折半查找法。是计算机中最基本、最有用的基础算法之一。它讲述的是在有序的集合中搜索特定目标的过程。
实现方法:首先将序列进行排序,将中间位置的值与目标值进行比较,如果相等,则查找成功;如果不等,则根据记录到的中间位置将序列分成前后两个子序列,比较目标值与中间位置值的大小,判断目标值所在的子序列,继续查找该序列,舍弃另外一个子序列。重复以上过程,直到查找成功,或者子序列不存在的时则表示目标值查找不成功。
二分查找法一般分成三个步骤:
1、预处理阶段:主要是对原集合进行预处理。例如数列是无序的,需要先进行排序。
2、查找阶段:使用递归或者循环的方式,把查找的空间划分成两半。
3、后处理阶段:清除掉不符合需求的一半,在剩余的一半空间中确定可行的候选者。
二分法模板:基于对左、中、右索引的分配,以及终止条件和后处理的不同,可以总结出以下三个简易模板。
基础模板一:
初始条件:left=0, right=length-1
终止条件:left>right
向左查找:right=mid-1
向右查找:left=mid+1
说明:基础模板,不需要与查找元素两侧进行比较来确定查找条件,也不需要后处理操作。到达末尾没找到,则说明数列中没有目标值。
基础模板二:
初始条件:left=0, right=length-1
终止条件:left+1==right
向左查找:right=mid
向右查找:left=mid
说明:需要使用搜索元素的左右邻居来确定查找方向是向左还是向右,因此它需要保证空间的每个步骤内至少有3个元素。当剩余2个元素的时候结束循环或者递归,而且还需要判断这2个元素是否符合条件。
基础模板三:
初始条件:left=0, right=length
终止条件:left==right
向左查找:right=mid
向右查找:left=mid+1
说明:需要使用搜索元素的右邻居来确定查找方向是向左还是向右,因此它需要保证空间的每个步骤内至少有2个元素。当剩余1个元素的时候结束循环或者递归,而且还需要判断这个元素是否符合条件。
时间复杂度:O(logn)
空间复杂度:O(1)