二分查找，必须保证待查找的数组是有序的，这里实现了两种方法，第一种是非递归实现，第二种是递归实现，java代码如下所示：
package algorithm; public class BinarySearch { /* * @author pardy * 二分查找 非递归 * 查找一个数在数组中的位置 * 数组必须有序 * @param srcArray * 有序数组 * @param des * 查找元素 * @return des在数组中的下标，没有返回-1 */ public static int binarySearch(int[] srcArray,int des){ int low=0; int high=srcArray.length-1; while(low<=high){ int middle = (low+high)/2; if(srcArray[middle]<des){ low=middle+1; }else if(srcArray[middle]>des){ high=middle-1; }else{ return middle; } } return -1; } /* * @author pardy * 递归实现二分查找 * @param srcArray * 有序数组 * @param des * 查找元素 * @param beginIndex * 开始位置 * @param endIndex * 结束位置 * @return des在数组中的下标，没有返回-1 * */ public static int recuBinarySearch(int[] srcArray,int des,int beginIndex,int endIndex){ int middle = (beginIndex + endIndex)/2; if(des <srcArray[beginIndex]||des>srcArray[endIndex]||beginIndex>endIndex){ return -1; } if(srcArray[middle]<des){ return recuBinarySearch(srcArray,des,middle+1, endIndex); }else if(srcArray[middle]>des){ return recuBinarySearch(srcArray,des,beginIndex, middle-1); }else{ return middle; } } public static void main(String[] args) { int[] src = new int[] {1, 3, 5, 7, 8, 9}; System.out.println("非递归下，数组中下标："+binarySearch(src, 8)); System.out.println("递归下，数组中下标："+recuBinarySearch(src, 8,0,src.length-1)); } }
