认识:
猜字游戏
步数 | 所猜的数 | 结果 | 可能值的范围 |
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 |