Java编程内功-数据结构与算法「二分查找非递归」

也想出现在这里？点击联系我~

基本介绍

1.二分查找只适用于从有序的数列中进行查找(比如数字和字母)，将数列排序后再进行查找。

2.二分查找法的运行时间为对数时间O(log2n),即查找到需要的目标位置最多只需log2n步，假设从[0,99]的队列中寻找目标数30，则需要查找步数为log2(100)，即最多需要7次(2^6<100<2^7)。

代码案例

1. packagecom.xie.algorithm;
3. publicclassBinarySearchNoRecur{
4. publicstaticvoidmain(String[]args){
5. int[]arr={1,3,8,10,11,67,100};
6. intindex=binarySearch(arr,1);
7. System.out.println("index="+index);
8. }
10. /**
11. *二分查找非递归实现
12. *
13. *@paramarr待查找的数组,arr是升序排列
14. *@paramtarget需要查找的数
15. *@return返回对应的下标，-1表示没有找到
16. */
17. publicstaticintbinarySearch(int[]arr,inttarget){
18. intleft=0;
19. intright=arr.length-1;
20. while(left<=right){
21. intmid=(left+right)/2;
22. if(arr[mid]==target){
23. returnmid;
24. }elseif(arr[mid]>target){
25. //需要向左边查找
26. right=mid-1;
28. }else{
29. //需要向右边查找;
30. left=mid+1;
31. }
32. }
33. return-1;
34. }
35. }

基本介绍

1.插值查找算法类似于二分查找，不同的是插值查找每次从自适应的mid处开始查找。

2.二分查找中求mid索引的公式转成插值查找mid索引公式，low表示左边的索引，high表示右边的索引，key表示要查找的值

代码案例

1. packagecom.xie.search;
3. importjava.util.ArrayList;
4. importjava.util.List;
6. publicclassInsertValueSearch{
7. staticintcount=0;
9. publicstaticvoidmain(String[]args){
10. int[]arr=newint[102];
11. arr[0]=1;
12. arr[1]=1;
13. for(inti=2;i<102;i++){
14. arr[i]=i;
15. }
16. List<Integer>indexList=insertValueSearch(arr,0,arr.length-1,1);
17. System.out.println("indexList="+indexList);
18. System.out.println("查找次数："+count);
20. /*
21. indexList=[1,0]
22. 查找次数：1
23. */
24. }
26. /**
27. *插值查找，返回索引集合
28. *
29. *@paramarr数组
30. *@paramleft左边索引
31. *@paramright右边索引
32. *@paramfindValue要查找的值
33. *@return找到就返回所有索引的集合，没有就返回空
34. */
35. publicstaticList<Integer>insertValueSearch(int[]arr,intleft,intright,intfindValue){
36. count++;
37. List<Integer>indexList=newArrayList<Integer>();
38. //注意：findValue<arr[0]||findValue>arr[arr.length-1]这个必须要，否则mid可能越界
39. if(left>right||findValue<arr[0]||findValue>arr[arr.length-1]){
40. returnnewArrayList<Integer>();
41. }
42. intmid=left+(right–left)*(findValue-arr[left])/(arr[right]-arr[left]);
43. intmidValue=arr[mid];
45. if(findValue>midValue){
46. returninsertValueSearch(arr,mid+1,right,findValue);
47. }elseif(findValue<midValue){
48. returninsertValueSearch(arr,left,mid-1,findValue);
49. }else{
50. //如果找到了，再向左扫描，将满足条件的加入indexList
51. inttemp=mid-1;
52. while(true){
53. if(temp<0||arr[temp]!=findValue){
54. break;
55. }
56. indexList.add(temp);
57. temp–;
58. }
60. //再向右扫描,将满足条件的加入indexList
61. temp=mid+1;
62. while(true){
63. if(temp>right||arr[temp]!=findValue){
64. break;
65. }
66. indexList.add(temp);
67. temp++;
68. }
69. indexList.add(mid);
70. returnindexList;
71. }
72. }
73. }

注意事项

1. 对于数据量大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。
2. 关键字分布不均匀的情况下，该方法不一定比二分法要好。

原文地址：https://www.toutiao.com/i6939142586317799968/