剑指Offer——二分查找算法
前言
本片博文主要讲解查找算法的相关知识。重点介绍二分查找。
二分查找算法是在有序数组中用到的较为频繁的一种查找算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)。
在面试的时候二分查找是用的比较多一种查找算法，如何在面试官面前快速准确得的写出代码决定你是否能够被录取。以前一直以为二分查找很简单，所以就没怎么重视，但是真要在面试官面前对着黑板手写出来，还是漏洞百出。
注
1.二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。
2.二分查找的一个条件是待查询的数组是有序的，我们假设这里的数组是升序的。
3.二分查找的主要思路就是设定两个指针start和end分别指向数组元素的首尾两端，然后比较数组中间结点arry[mid]和待查找元素。如果待查找元素小于中间元素，那么表明带查找元素在数组的前半段，那么将end=mid-1，如果待查找元素大于中间元素，那么表明该元素在数组的后半段，将start=mid+1;如果中间元素等于待查找元素，那么返回mid的值。
譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
1.第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找；
2.寻找{6， 7， 8， 9}的中位数，为8，8>6，则6应该在8左边的数组元素中，那么就在｛6，7，8｝中查找；
3.寻找{6， 7， 8}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
二分查找算法就是不断将数组进行对半分割，每次拿中间元素和goal进行比较。
源码
-
package cn.edu.ujn.demo;
-
-
public class BinarySearch {
-
-
/**
-
* @param args
-
*/
-
public static void main(String[] args) {
-
int [] array = {1,2,3,4,4,7,12};
-
int len = array.length;
-
//System.out.println(binarySearchRecursion(array, 7, array[0], array[len-1]));
-
System.out.println(binarySearchRecursionNon(array, 7, array[0], array[len-1]));
-
}
-
/**
-
* 二分查找(递归)
-
* @param arry 递增数组
-
* @param value 待查找数值
-
* @param start 起始查找位置
-
* @param end 末查找位置
-
* @return
-
*/
-
private static int binarySearchRecursion(int arry[],int value,int start,int end)
-
{
-
if(start > end)
-
return -1;
-
-
int mid=start + (end-start)/2;
-
if(arry[mid] == value)
-
return mid;
-
-
else if(value < arry[mid])
-
{
-
end = mid - 1;
-
return binarySearchRecursion(arry,value,start,end);
-
}
-
else
-
{
-
start = mid + 1;
-
return binarySearchRecursion(arry,value,start,end);
-
}
-
}
-
/**
-
* 二分查找(非递归)
-
* @param arry 递增数组
-
* @param value 待查找数值
-
* @param start 起始查找位置
-
* @param end 末查找位置
-
* @return
-
*/
-
private static int binarySearchRecursionNon(int arry[],int value,int start,int end)
-
{
-
while(start <= end){
-
int mid=start + (end-start)/2;
-
-
if(arry[mid] == value)
-
return mid;
-
-
else if(value < arry[mid])
-
{
-
end = mid - 1;
-
}
-
-
else
-
start = mid + 1;
-
}
-
return -1;
-
}
-
}
在轮转后的有序数组上应用二分查找法
之前我们说过二分法是要应用在有序的数组上，如果是无序的，那么比较和二分就没有意义了。
不过还有一种特殊的数组上也同样可以应用，那就是“轮转后的有序数组（Rotated Sorted Array）”。它是有序数组，取其中某一个数为轴，将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲，有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。
下边就是二分查找法在轮转后的有序数组上的实现（假设数组中不存在相同的元素）
-
/**
-
* 在轮转后的有序数组上应用二分查找法
-
* @param array
-
* @param low
-
* @param high
-
* @param target
-
* @return
-
*/
-
int searchInRotatedSortedArray(int array[], int low, int high, int target)
-
{
-
while(low <= high)
-
{
-
int mid = (low + high) / 2;
-
if (target < array[mid])
-
if (array[mid] < array[high]) // the higher part is sorted
-
high = mid - 1; // the target would only be in lower part
-
else // the lower part is sorted
-
if(target < array[low]) // the target is less than all elements in low part
-
low = mid + 1;
-
else
-
high = mid - 1;
-
-
else if(array[mid] < target)
-
if (array[low] < array[mid]) // the lower part is sorted
-
low = mid + 1; // the target would only be in higher part
-
else // the higher part is sorted
-
if (array[high] < target) // the target is larger than all elements in higher part
-
high = mid - 1;
-
else
-
low = mid + 1;
-
else // if(array[mid] == target)
-
return mid;
-
}
-
return -1;
-
}
对比普通的二分查找法，为了确定目标数会落在二分后的哪个部分，我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。
二分查找法的缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：
必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，自能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。
注
我们知道在效率方面，传值调用要比传址调用来的低，因为传值调用要进行一次变量的拷贝，而传址调用则是直接对这个变量进行操作。因此在编程中我们应该尽量将参数改为传址调用。
美文美图
文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。
原文链接：shq5785.blog.csdn.net/article/details/52102179