二分查找算法原理及常见面试题

相关面试题

（1）二分查找算法的原理是什么？★★★★☆

（2）写一个函数，实现对一个整型有序数组的二分查找。★★★★☆

（3）如何使用二分查找算法求解平方根？★★☆☆☆

二分查找法原理

二分查找算法又叫作折半查找算法，要求待查找的序列有序，每次查找都取中间位置的值与待查关键字进行比较，如果中间位置的值比待查关键字大，则在序列的左半部分继续执行该查找操作，如果中间位置的值比待查关键字小，则在序列的右半部分继续执行该查找操作，直到找到关键字为止，否则在序列中没有待查关键字。

如图9-1所示，在有序数组[3,4,6,20,40,45,51,62,70,99,110]中查找key=20的数据，根据二分查找算法，只需查找两次便能命中数据。这里需要强调的是，二分查找算法要求要查找的集合是有序的，如果不是有序的集合，则先要通过排序算法排序后再进行查找。

二分查找算法的Java实现如下：

public static int binarySearch(int []array,int a){ int low=0; int high=array.length-1; int mid; while(lowarray[mid]){ //向右查找 low=mid+1; }else{ //向左查找 high=mid-1; } } return -1; }

以上代码定义了binarySearch方法用于二分查找，在该方法中有3个变量low、mid和 high，分别表示二分查找的最小、中间和最大的数据索引。在以上代码中，通过一个while 循环在数组中查找传入的数据，在该数据大于中间位置的数据时向右查找，即最大索引位置不变，将最小索引设置为上次循环的中间索引加1；在该数据小于中间位置的数据时向左查找，即最小索引位置不变，然后将最大索引设置为上次循环的中间索引并减1。重复以上过程，直到中间索引位置的数据等于要查找的数据，说明找到了要查找的数据，将该数据对应的索引返回。如果遍历到low>high仍没有找到待查找的数据，则说明该数据在列表中不存在，返回-1。

内容摘自《Offer来了（第2版）》。这是一本超强Java面试宝典、面霸手册，超详尽的Java知识点速查，Java面试题库，帮你深入理解Java核心技术，对Java知识点查漏补缺，可作为工具书使用。