二分查找方法
二分查找经常用来在有序的数列查找某个特定的位置。因此，应用二分查找法，这个数列必须包含以下特征：
- 存储在数组中
- 有序排列
二分查找方法不适用于链表，因为链表方法需要遍历，应用二分查找法意义不大。
一般情况下，我们默认数组是单调递增数列，且无重复元素。（有重复元素的题应该如何解决）
二分查找方法递归和非递归实现
第一种是递归方法实现，递归方法一般走的比较深，容易超时：
1 public int binarySearch( int [] A, int low, int high, int target){ 2 if (low > high) 3 return -1; 4 5 int mid = (low + high)/2; 6 if (A[mid]> target) 7 return binarySearch(array, low, mid -1, target); 8 if (array[mid]< target) 9 return binarySearch(array, mid+1, high, target); 10 11 if (A[mid] == target) 12 return mid; 13 }
第二种是非递归实现方法，更常用一些：
1 public int binarySearch( int[] A, int low, int high, int target){ 2 if(low > high) 3 return -1; 4 5 while(low<=high){ 6 int mid = low+high/2; 7 if(A[mid] == target) 8 return mid; 9 if(A[mid] > target) 10 high = mid-1; 11 if(A[mid] < target) 12 low = mid+1; 13 } 14 return -1; 15 }
Rotated Sorted Array
这是二分查找方法的一个变种，在leetcode中出现过。
它是有序数组，取期中某一个数为轴，将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲，有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。
1 public int SearchInRotatedSortedArray( int [] array, int low, int high, int target) 2 { 3 while(low <= high) 4 { 5 int mid = (low + high) / 2; 6 if (target < array[mid]) 7 if (array[mid] < array[high]) // the higher part is sorted 8 high = mid - 1; // the target would only be in lower part 9 else // the lower part is sorted 10 if(target < array[low]) // the target is less than all elements in low part 11 low = mid + 1; 12 else 13 high = mid - 1; 14 15 else if(array[mid] < target) 16 if (array[low] < array[mid]) // the lower part is sorted 17 low = mid + 1; // the target would only be in higher part 18 else // the higher part is sorted 19 if (array[high] < target) // the target is larger than all elements in higher part 20 high = mid - 1; 21 else 22 low = mid + 1; 23 else // if(array[mid] == target) 24 return mid; 25 } 26 27 return -1; 28 }
二分查找缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：
必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是平衡二叉树了，自能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。
二分查找其他应用
1. 寻找上下界
2. 寻找范围
本文基于：http://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html