数据结构和算法之:二分法demo

时间:2021-05-01 10:37:20
package com.js.ai.modules.pointwall.testxfz;
class OrdArray{
	private long[] a;
	private int nElems;
	public OrdArray(int max) {
		a=new long[max];
		nElems=0;
	}
	public int size(){
		return nElems;
	}
	//插入方法
	public void insert(long value){
		int j;
		for(j=0;j<nElems;j++){
			if(a[j]>value)
				break;
		}
		for(int k=nElems;k>j;k--){
			a[k]=a[k-1];
		}
		a[j]=value;
		nElems++;
	}
	
	//删除方法
	public boolean delete(long value){
		int j=find(value);
		if(j==nElems){
			return false;
		}else {
			for(int k=j;k<nElems;k++){
				a[k]=a[k+1];
			}
			nElems--;
			return true;
		}
	}
	
	//二分查找
	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;
				}
			}
		}
	}
	
	public void display(){
		for(int j=0;j<nElems;j++){
			System.out.print(a[j]+" ");
		}
		System.out.print("");
	}
}
public class OrdArrayTest {
public static void main(String[] args) {
	int maxSize=100;
	OrdArray arr;
	arr=new OrdArray(maxSize);
	arr.insert(77);
	arr.insert(00);
	arr.insert(11);
	arr.insert(22);
	arr.insert(88);
	arr.insert(99);
	arr.insert(33);
	arr.insert(55);
	arr.insert(44);
	arr.insert(66);
	int searchKey=55;
	if(arr.find(searchKey)!=arr.size()){
		System.out.println("Found:"+searchKey);
	}else {
		System.out.println("can not found:"+searchKey);
	}
	arr.display();
	arr.delete(00);
	arr.delete(55);
	arr.delete(99);
	System.out.println("\r\n===");
	arr.display();
}
}