算法要求:
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
算法复杂度:
二分查找的基本思想是将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(接下来操作元素的剩余个数),其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,(是以2为底,n的对数)
所以时间复杂度可以表示O(h)=O(log2n)
算法实现(java):
public class ErFenTest { public static int recursionBinarySearch(int[] arr,int key,int low,int high){ if(key < arr[low] || key > arr[high] || low > high){ return -1; } int middle = (low + high) / 2; //初始中间位置 if(arr[middle] > key){ //比关键字大则关键字在左区域 return recursionBinarySearch(arr, key, low, middle - 1); }else if(arr[middle] < key){ //比关键字小则关键字在右区域 return recursionBinarySearch(arr, key, middle + 1, high); }else { return middle; } } /** * 不使用递归的<a href="https://www.wangt.cc/tag/%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be/" title="查看更多关于二分查找的文章" target="_blank">二分查找</a> *title:commonBinarySearch *@param arr *@param key *@return 关键字位置 */ public static int commonBinarySearch(int[] arr,int key){ int low = 0; int high = arr.length - 1; int middle = 0; //定义middle if(key < arr[low] || key > arr[high] || low > high){ return -1; } while(low <= high){ middle = (low + high) / 2; if(arr[middle] > key){ //比关键字大则关键字在左区域 high = middle - 1; }else if(arr[middle] < key){ //比关键字小则关键字在右区域 low = middle + 1; }else{ return middle; } } return -1; //最后仍然没有找到,则返回-1 } /** * 使用递归的<a href="https://www.wangt.cc/tag/%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be/" title="查看更多关于二分查找的文章" target="_blank">二分查找</a> *title:recursionBinarySearch *@param arr 有序数组 *@param key 待<a href="https://www.wangt.cc/tag/%e6%9f%a5%e6%89%be/" title="查看更多关于查找的文章" target="_blank">查找</a>关键字 *@return 找到的位置 */ public static void main(String[] args){ int[] tem={1,2,3,4,5,6,7,8}; //test 递归 System.out.println("<a href="https://www.wangt.cc/tag/%e6%9f%a5%e6%89%be/" title="查看更多关于查找的文章" target="_blank">查找</a>结果所在的位置: "+ErFenTest.recursionBinarySearch(tem,3,0,tem.length-1)); //test 非递归 System.out.println("<a href="https://www.wangt.cc/tag/%e6%9f%a5%e6%89%be/" title="查看更多关于查找的文章" target="_blank">查找</a>结果所在的位置: "+ErFenTest.commonBinarySearch(tem,3)); } }