二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 1、首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 2、重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。时间复杂度为O(log2n)。
public class Binary { public static void main(String[] args) { int[] array = {1,2,4,5,7,9,13}; int index = binarySort(array,4); System.out.println(index); } public static int binarySort(int[] array, int des){ int start = 0; int end = array.length - 1; while(start <= end){ int middle = (start + end)/2; //注释中间的代码用于显示查找效果,与排序无关 /*********************/ for(int value : array){ String ret = " " + value; if(value == array[middle]) ret = "#" + value; System.out.print(ret); } System.out.println(); /********************/ if(array[middle] == des){ return middle; }else if(array[middle] > des){ end = middle - 1; }else{ start = middle + 1; } } return -1; } }输出结果：
1 2 4#5 7 9 13 1#2 4 5 7 9 13 1 2#4 5 7 9 13 2