Java编程技巧-数据结构与算法《二分查找非递归》

基本介绍1、二分查找只适用于从有序数组（如数字、字母）开始查找，在查找前先对数组进行排序。2、二分查找法的运行时间为对数时间O(log2n)，即最多只需要log2n步就可以找到所需的目标位置。假设从[0,99]的队列中目标数量为30个，需要搜索的步数为log2(100)，即最多需要7次(2^6<100<2^7).代码示例packagecom.xie.algorithm;publicclassBinarySearchNoRecur{publicstaticvoidmain(String[]args){int[]arr={1,3,8,10,11,67,100};intindex=binarySearch(arr,1);System.out。println("index="+index);}/***二分查找非递归实现**@paramarr待查找数组，arr为升序*@paramtarget待查找数*@return返回对应下标，-1表示未找到*/publicstaticintbinarySearch(int[]arr,inttarget){intleft=0;intright=arr.length-1;while(left<=right){intmid=(left+right)/2;if(arr[mid]==target){returnmid;}elseif(arr[mid]>target){//需要向左搜索right=mid-1;}else{//需要向右搜索;left=mid+1;}}return-1;}}基本介绍1.插值搜索算法与二分查找类似，不同的是插值搜索每次都是从自适应mid开始。2.将二分查找mid索引的公式转化为mid索引的插值查找公式，low表示左边的索引，high表示右边的索引，key表示要查找的值代码casepackagecom.xie.search;importjava.util.ArrayList;导入java.util.List；publicclassInsertValueSearch{staticintcount=0;publicstaticvoidmain(String[]args){int[]arr=newint[102];arr[0]=1;arr[1]=1;for(inti=2;i<102;i++){arr[i]=i;}ListindexList=insertValueSearch(arr,0,arr.length-1,1);System.out.println("indexList="+indexList);System.out.println("搜索次数："+count);/*indexList=[1,0]搜索次数：1*/}/***插值搜索，返回索引集合**@paramarr数组*@paramleftleftIndex*@paramrightrightindex*@paramfindValue要搜索的值*@return如果找到则返回所有索引的集合，否则返回空*/publicstaticListinsertValueSearch(int[]arr,intleft,intright,intfindValue){计数++;ListindexList=newArrayList();//注意：findValuearr[arr.length-1]必须要，否则mid可能越界if(left>right||findValuearr[arr.length-1]){returnnewArrayList();}intmid=left+(right-left)*(findValue-arr[left])/(arr[right]-arr[left]);intmidValue=arr[mid];if(findValue>midValue){returninsertValueSearch(arr,mid+1,right,findValue);}elseif(findValueright||arr[temp]!=findValue){break;}indexList.add(temp);temp++;}indexList.add(mid);returnindexList;}}}量大的注意事项的数据，对于关键字分布比较均匀的查找表，采用插值搜索，速度更快。在关键词分布不均匀的情况下，这种方法不一定比二分法好。