java数组之二分法查找

认识：

　　猜字游戏

步数	所猜的数	结果	可能值的范围
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代码：

 package com.test;

 /**

  * 二分查找

  * @author jingxin

  *

  */

 public class Test {

     public static void main(String[] args) {

         OrdArray array = new OrdArray(5);

         array.insert(21);

         array.insert(1);

         array.insert(3);

         array.insert(4);

         array.insert(10);

         array.display();

         int i = array.find(3);

         System.out.println("二分查找："+i);

         array.delete(1);

         array.display();

     }

 }

 class OrdArray{

     private long[] a; //数组

     private int nElems;  //数组下标

     public OrdArray(int max){

         a = new long[max]; //初始化数组

         nElems = 0;

     }

     /**

      * 返回数组的长度

      * @return

      */

     public int size(){

         return nElems;

     }

     /**

      * 二分查找

      * @param searchKey 待查找的数

      * @return

      */

     public int find(long searchKey){

         int lowerBound = 0; // 二分起始下标

          int upperBound = nElems -1; // 二分终点下标

         int  curIn; // 二分对半下标

         while(true){

　　
　　　　　　　　　 //对于偶数个数据项，中间值只取整数，不影响查找结果　　
             curIn = (lowerBound + upperBound)/2;

             if(a[curIn] == searchKey){

                 return curIn;  // 找到了

             } else if(lowerBound > upperBound){

                 return nElems; // 找不到返回元素个数

             } else{

                 if(a[curIn] < searchKey){

                     lowerBound = curIn + 1;

                 } else{

                     upperBound = curIn - 1;

                 }

             }

         }

     }

     /**

      * 升序添加数组元素

      * @param value

      */

     public void insert(int value){

         int i;

         for (i = 0; i < nElems; i++) {

             if(a[i] > value){  // 线性查找,i存放符合条件的顺序元素

                 break;

             }

         }

         for (int k = nElems; k>i; k--) { // 移动较大的数往上移

             a[k] = a[k-1];

         }

         a[i] = value;

         nElems++;

     }

     /**

      * 删除数组元素

      * @param value

      * @return

      */

     public boolean delete(long value){

         int i = find(value);

         // eg:5个数则，nElems=5，而i只能是0~4

         if(i == nElems){

             return false; // 该元素不存在

         } else{

             for (int k = i; k < nElems-1; k++) { // 将更大的数往下移

                 a[k] = a[k+1];

             }

             nElems--;

             return true;

         }

     } 

     /**

      * 查看数组

      */

     public void display(){

         for (int i = 0; i < nElems; i++) {

             System.out.print(a[i]+ " ");

         }

         System.out.println("");

     }

 }

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

范围	所需比较次数	该次数能查找的最大范围
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

巴特西

java数组之二分法查找

最新文章

热门文章