运行截图:
线性查找的效率当然不是很高效,最坏情况是数组中没有我们要找的目标值,但是我们还是要遍历完整个数组才能知道。但是它的优点就是很简单,特别的简单,而且它还不要求待查找的数组是有序的。
二分查找(英语:binary search),也称折半查找(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的 那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分法首先考察中间元素a[mid],如果该值是我们要找的值,那好极了,直接找到了;如果不是的话,由于我们已经知道数组是排好序的(二分法要求待查找的数组是有序的,本例假设是升序的,降序其实是一样的),那就看目标值target和a[mid]的关系是怎样的:如果a[mid] > target则说明目标值target如果存在的话,一定在a[mid]的左侧,因为左侧都比a[mid]小;如果a[mid] < target则说明目标值如果存在的话一定在a[mid]的右侧,因为右侧都比a[mid]大。
因为a[mid]处在数组的中间位置,所以它的左侧或者右侧都是数组的一半,这样每一次我们通过a[mid]和target的比较就可以排除掉一半的数据。最后只有两种情况,要么我们找到了目标值,要么我们排除了所有数据没有找到目标值。
由此看来,在处理已排序数据的查找工作时,二分查找法显然效率高于线性查找法。这种优势在数据量越大的时候越明显。
比如说,现在有序数组中含有100万个数据,我们要求查找特定元素。如果使用线性查找法,我们必须对这一100万个数据依次考察以确定出目标元素是不是存在,最好的情况是目标元素在数组的第一个位置a[0],这样只要一次就查找到目标元素了,最坏情况是目标元素在数组的最后a[999999],这样我们就得比较100万次才能知道目标元素到底在不在,平均下来看的话也需要50万次比较。而如果使用二分查找法,我们大约做20次比较就可以知道目标元素是不是存在于数组中了。
50万 VS 20!
是不是很惊悚?为了达到目的我们可以使用不同的算法,但是这些算法之间的差异真的很大! 在数据量越大的时候二分法的优势越明显。
非递归两种方式的代码实现
递归的二分查找方式