java数据结构与算法---有序数组的二分查找

之前学校开了数据结构这门课，是C语言版的，没认真学，只好现在来补一补了

首先要说的是必须是有序的，不然是没办法用二分法查找的

1.有序数组优缺点

优点:查找速度（采用二分查找法）比无序数组快很多(查找的数据量越大，优势越明显)

下面是一组用二分法查找的数据:

数据量                                                               所需比较次数

10                                                                            4

100                                                                          7

1000                                                                        10

10000                                                                      14

100000                                                                    17

1000000                                                                   20

10000000                                                                 24

100000000                                                               27

缺点:插入时需要将后面的元素进行移动

2.然后下面是我实现有序数组二分查找的代码:

package ordarray;
/**
 * 有序数组
 * @author zhang
 *
 */
public class OrdArray {
	private long[] a;
	private int nElems;
	
	public OrdArray(int max){
		a= new long[max];
		nElems=0;
	}

	//二分查找方法
	public int find(long serachKey){
		int lowerBound=0;
		int upperBound=nElems-1;
		int curIn;
		while(true){
			curIn=(lowerBound+upperBound)/2;
			if(a[curIn]==serachKey){
				return curIn;
			}else if(lowerBound>upperBound){
				return nElems;
			}else{
				if(a[curIn]<serachKey){//往后查
					lowerBound=curIn+1;//改变最小索引
				}else{//往前查
					upperBound=curIn-1;//改变最大索引
				}				
			}
		}
	}
	//二分法删除
	public boolean delete2(long value){
		int i=find(value);
		if(i==nElems){
			return false;
		}else{
			for(int j=i;j<nElems;j++){
				a[j]=a[j+1];
			}
			nElems--;
			return true;
		}
	}
	
	public int size(){//查看大小，元素个数
		return nElems;
	}
	
	//添加数据(线性查找添加)插入一定是可以插入的，不像删除要查看要删除的元素是否存在
	//从小到大排序插入
	public void insert(long value){
		int i;
		for(i=0;i<nElems;i++){
			if(a[i]>value){
				break;
			}
		}
		//j>i每次判断j是否大于我们停止的i位置
		for(int j=nElems;j>i;j--){
			//必须从最后一个开始移
			a[j]=a[j-1];				
		}
		//最后插入我们要插入的元素
		a[i]=value;	
		nElems++;
	}
	
	//删除
	public boolean delete(long value){
		int i;
		for(i=0;i<nElems;i++){
			if(a[i]==value){
				break;
			}
		}
		if(i==nElems){
			System.out.println("删除失败,没有"+value+"这个值");
			return false;
		}else{
			for(int j=i;j<nElems;j++){
				a[j]=a[j+1];
			}
			nElems--;
			return true;
		}			
		
	}
	
	public void display(){
		for(int i=0;i<nElems;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
}

 

package ordarray;

public class OrderedApp {
	public static void main(String[] args) {
		int maxSize=100;
		OrdArray arr;
		arr=new OrdArray(maxSize);
		arr.insert(77);
		arr.insert(66);
		arr.insert(76);
		arr.insert(79);
		arr.insert(44);
		arr.insert(55);
		arr.insert(34);
		arr.insert(23);
		arr.insert(66);
		arr.insert(97);
		int serachKey=76;
		if(arr.find(serachKey)!=arr.size()){
			System.out.println("找到了"+serachKey);
		}else{
			System.out.println("没有找到"+serachKey);
		}
		arr.display();
		
		arr.delete2(23);
		arr.delete2(66);
		arr.display();
	}
}