目前在剑指offer中遇到的题和常用的折半查找算法，如果再遇到再追加总结
##一般的折半查找算法
package althorgrim; /** * 1、必须采用顺序存储结果 * 2、关键字必须有序 */ public class TestBinarySearch { public static int binarySearch(int a[],int goal){ int high=a.length-1; // 设定最高位置的下标 int low=0; // 设定最低位置的下标 while (low<=high) { // 如果low》high则跳出，就是没找到 int middle=(low+high)/2; // 设定中间位置的下标 if (a[middle]==goal) { // 如果中间正好是，那么直接返回位置就好 return middle; } else if (a[middle]>goal) { //如果中间值大于该值，说明该值在中间值左边区间，所以令high=middle-1，在左侧区间继续查找 high=middle-1; } else { //如果中间值小于该值，说明该值在中间值右边区间，所以令high=middle-1，在右侧区间继续查找 low=middle+1; } } return -1; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] src = new int[] {1, 3, 5, 7, 8, 9}; System.out.println(binarySearch(src, 3)); } }
##旋转数组的折半查找算法
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
package Arrays; public class Solution { public int minNumberInRotateArray(int[] array) { int low = 0 ; int high = array.length - 1; //分别是第一个元素和最后一个元素的下标 while(low <= high){ int mid = (high + low) / 2; //获取了中间元素的下标 if(array[mid] > array[high]){ //如果中间元素大于最高的，说明最小值在中间元素右边 low = mid + 1; }else if(array[mid] == array[high]){ high = high - 1; }else{ high = mid;//如果中间元素小于最高的，说明最小值在中间元素左边或者就是中间元素 } } return array[low]; } public static void main(String[] args) { int[] array = { 3, 4, 5, 2, 2,3 }; Solution s = new Solution(); System.out.println(s.minNumberInRotateArray(array)); } }
