二分查找算法（BinarySearch）

思想

  二分查找也称折半查找，是一种效率较高的查找方法。   它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

要求

存储结构必须为线性结构。结构内元素必须按大小规则有序排列。

复杂度

时间复杂度：

  时间复杂度无非就是while循环的次数，总共有n个元素，渐渐跟下去就是n,n/2,n/4,…n/2^k（2的平方）（接下来操作元素的剩余个数），其中k就是循环的次数。   由于n/2^k 取整后>=1，   即令n/2^k=1，   可得k=log2n,（是以2为底，n的对数）   所以时间复杂度可以表示O(h)=O(log2n)。

代码实现

  核心类:

public class BinarySearch { public int search(int[] arr,int num){ int lift = 0; int right = arr.length - 1; int middle = (lift + right)/2; int index = -1; int count = 0;//记录查找次数 //防止下标越界 while (lift <= right){ ++count; if (num == arr[middle]){ index = middle; System.out.println("查找了"+count+"次"); return index; } if (num < arr[middle]){ right = middle -1; middle = (lift + right)/2; continue; } if (num > arr[middle]){ lift = middle + 1; middle = (lift + right)/2; continue; } } System.out.println("查找了"+count+"次"); return index; } }

  测试类:

public class BinarySearchTest { public static void main(String[] args) { int[] arr = new int[]{1,2,3,4,5,6,7,8,9}; int index; int number = 7; BinarySearch search = new BinarySearch(); index = search.search(arr,number); if (index == -1){ System.out.println("没找到"); return; } System.out.println("该元素的下标是："+index+"，是该数组的第"+(index+1)+"个元素"); } }

  测试结果:

查找了2次 该元素的下标是：6，是该数组的第7个元素