java数组之二分法查找

时间:2021-06-15 22:10:36

认识:

  猜字游戏

步数 所猜的数 结果 可能值的范围
0     1~100
1 50 太高 1~49
2 25 太低 26~49
3 37 太高 26~36
4 31 太低 32~36
5 34 太高 32~33
6 32 太低 33~33
7 33 正确  

 

 

 

 

 

 

 

 

 

 二分法要求:

  有序数列

有序数组的java代码:

  

  1 package com.test;
  2 
  3 /**
  4  * 二分查找
  5  * @author jingxin
  6  *
  7  */
  8 public class Test {
  9 
 10     public static void main(String[] args) {
 11 
 12         OrdArray array = new OrdArray(5);
 13         
 14         array.insert(21);
 15         array.insert(1);
 16         array.insert(3);
 17         array.insert(4);
 18         array.insert(10);
 19         
 20         array.display();
 21         
 22         int i = array.find(3);
 23         System.out.println("二分查找:"+i);
 24         
 25         array.delete(1);
 26         
 27         array.display();
 28 
 29     }
 30     
 31     
 32     
 33 
 34 }
 35 
 36 
 37 class OrdArray{
 38     private long[] a; //数组
 39     private int nElems;  //数组下标
 40     
 41     public OrdArray(int max){
 42         a = new long[max]; //初始化数组
 43         nElems = 0;
 44     }
 45     
 46     /**
 47      * 返回数组的长度
 48      * @return
 49      */
 50     public int size(){
 51         return nElems;
 52     }
 53     
 54     /**
 55      * 二分查找
 56      * @param searchKey 待查找的数
 57      * @return
 58      */
 59     public int find(long searchKey){
 60         int lowerBound = 0; // 二分起始下标
 61          int upperBound = nElems -1; // 二分终点下标
 62         int  curIn; // 二分对半下标
 63         
 64         while(true){
  
          //对于偶数个数据项,中间值只取整数,不影响查找结果  
65 curIn = (lowerBound + upperBound)/2; 66 if(a[curIn] == searchKey){ 67 return curIn; // 找到了 68 } else if(lowerBound > upperBound){ 69 return nElems; // 找不到返回元素个数 70 } else{ 71 if(a[curIn] < searchKey){ 72 lowerBound = curIn + 1; 73 } else{ 74 upperBound = curIn - 1; 75 } 76 } 77 } 78 79 } 80 81 /** 82 * 升序添加数组元素 83 * @param value 84 */ 85 public void insert(int value){ 86 int i; 87 for (i = 0; i < nElems; i++) { 88 if(a[i] > value){ // 线性查找,i存放符合条件的顺序元素 89 break; 90 } 91 } 92 for (int k = nElems; k>i; k--) { // 移动较大的数往上移 93 a[k] = a[k-1]; 94 } 95 a[i] = value; 96 nElems++; 97 } 98 99 /** 100 * 删除数组元素 101 * @param value 102 * @return 103 */ 104 public boolean delete(long value){ 105 int i = find(value); 106 // eg:5个数则,nElems=5,而i只能是0~4 107 if(i == nElems){ 108 return false; // 该元素不存在 109 } else{ 110 for (int k = i; k < nElems-1; k++) { // 将更大的数往下移 111 a[k] = a[k+1]; 112 } 113 nElems--; 114 return true; 115 } 116 117 118 119 120 } 121 122 /** 123 * 查看数组 124 */ 125 public void display(){ 126 for (int i = 0; i < nElems; i++) { 127 System.out.print(a[i]+ " "); 128 } 129 System.out.println(""); 130 } 131 132 }

 

二分查找所需的比较次数对照表:

范围 所需比较次数 该次数能查找的最大范围
10 4 16=2^4
100 7 128=2^7
1千 10 1024=2^10
1万 14 2^14
10万 17 2^17
100万 20 2^20
1000万 24 2^24
1亿 27 2^27