【转】第一课 有序数组及其二分法查找

有序数组可以采用二分法查找关键字，先是一个有序数组类

package com.flysnow.chap02;   
  
/**  
 * 递增有序数组，采用二分法查找数据  
 * @author 飞雪无情  
 * @since:2010-2-26  
 */  
public class OrdArray {   
    private int[] array;   
    private int nElem;   
    //构造函数   
    public OrdArray(int max){   
        array=new int[max];   
    }   
    public OrdArray(OrdArray array){   
        this.array=array.getArray();   
        this.nElem=array.size();   
    }   
    //数组的个数   
    public int size(){   
        return nElem;   
    }   
    /**  
     * 采用二分法查找数据  
     * @param searchKey 查找关键字  
     * @return 关键字的下标  
     */  
    public int find(int searchKey){   
        int lowIndex=0;//最低下标   
        int highIndex=nElem-1;//最高下标   
        int index;//关键字的下标   
        while(true){   
            index=(lowIndex+highIndex)>>1;   
            if(array[index]==searchKey){//找到了   
                return index;   
            }else if(lowIndex>highIndex){   
                return nElem;//没有找到，返回数组的个数   
            }else{//还没有找完，继续查找   
                if(array[index]>searchKey){   
                    highIndex=index-1;   
                }else{   
                    lowIndex=index+1;   
                }   
            }   
        }   
    }   
    /**  
     * 插入数据  
     * @param value 要插入的数据  
     */  
    public void insert(int value){   
        int j;   
        for(j=0;j<nElem;j++){   
            if(array[j]>value){   
                break;   
            }   
        }   
        //数据移位   
        for(int k=nElem;k>j;k--){   
            array[k]=array[k-1];   
        }   
        array[j]=value;   
        nElem++;   
    }   
    /**  
     * 删除数据  
     * @param value 要删除的数据  
     * @return 是否删除  
     */  
    public boolean delete(int value){   
        int index=find(value);   
        if(index==nElem){//没有找到要删除的数据   
            return false;   
        }else{   
            for(int j=index;j<nElem;j++){   
                array[j]=array[j+1];   
            }   
            nElem--;   
            return true;   
        }   
    }   
    public int[] getArray() {   
        return array;   
    }   
    /**  
     * 显示  
     */  
    public void display(){   
        for(int i=0;i<nElem;i++){   
            System.out.println("array["+i+"]:"+array[i]);   
        }   
    }   
}  

有序数组的插入、删除、查找测试

package com.flysnow.chap02;   
  
/**  
 * @author 飞雪无情  
 * @since:2010-2-26  
 */  
public class OrdArrayApp {   
  
    /**  
     * @param args  
     */  
    public static void main(String[] args) {   
        OrdArray array=new OrdArray(100);   
        array.insert(0);   
        array.insert(10);   
        array.insert(9);   
        array.insert(8);   
        array.insert(3);   
        array.insert(5);   
        array.insert(6);   
        array.insert(2);   
        array.insert(1);   
        array.insert(7);   
        array.insert(4);   
        array.display();   
        int searchKey=9;   
        //查找   
        int index=array.find(searchKey);   
        System.out.println(index==array.size()?"没有找到关键字:"+searchKey:"找到关键字下标为："+index);   
        //删除   
        if(array.delete(searchKey)){   
            System.out.println("成功删除："+searchKey);   
            array.display();   
        }else{   
            System.out.println("没有找到要删除的关键字："+searchKey);   
        }   
    }   
  
}  

总结：有序数组的好处就是查找（二分法）速度快，但是插入的时候需要移动元素以腾出空间，所以较慢。
附上算法的复杂度的大O表示法图示：