package Array;

/**
 * 排序数组，向数组中添加元素时维护数组的有序性；
 * @author wl
 *
 */
public class MyOrderArray {
	private long array[];
	private int elements;//用于记录数组中实际数据的个数
	
	public MyOrderArray(){
		array=new long[50];//数组默认长度为50；
	}
	
	public MyOrderArray(int capacity){//设置数组的默认长度
		array=new long[capacity];
	}
	
	/**
	 * 向数组中插入元素，并维护数组中元素的有序性
	 */
	public void add(long data){
		if(elements>array.length-1){
			throw new ArrayIndexOutOfBoundsException();
		}
		
		int i;
		for(i=0;i<elements;i++){
			if(array[i]>data){
				break;
			}
		}
		
		for(int j=elements;j>i;j--){
			array[j]=array[j-1];
		}
		array[i]=data;
		elements++;
	}
	
	
	/**
	 * 删除index处的元素
	 * @param index
	 */
	public void delete(int index){
		if(index>=array.length||index<0){
			throw new IndexOutOfBoundsException();
		}
		for(int i=index;i<=elements;i++){
			array[i]=array[i+1];
		}
		elements--;
	}
	
	/**
	 * 删除元素data
	 * @param data
	 */
	public void delete(long data){
		int addr=search(data);
		if(addr==-1){
			System.out.println(data+"不存在");
		}else{
			for(int i=addr;i<=elements;i++){
				array[i]=array[i+1];
			}
			elements--;
		}
	}
	
	/**
	 * 用二分查找（折半查找）法查找数组中data的下标位置
	 * @param data
	 * @return
	 */
	public int binarySearch(long data){
		int low,high,mid;
		
		low=0;
		high=elements;
		
		while(low<=high){
			mid=low+(high-low)/2;
			
			if(data<array[mid]){
				high=mid-1;
			}else if(data>array[mid]){
				low=mid+1;
			}else{
				return mid;
			}
		}
		return -1;
	}
	/**
	 * 查找index处的元素
	 * @param index
	 * @return
	 */
	public long search(int index){
		if(index>=array.length||index<0){
			throw new IndexOutOfBoundsException();
		}
		return array[index];
	}
	
	/**
	 * 查找array中data值所在下标
	 * @param data
	 * @return
	 */
	public int search(long data){
		int i;
		for(i=0;i<=elements;i++){
			if(array[i]==data){
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 打印数组中的内容
	 */
	public void display(){
		System.out.print("[");
		for(int i=0;i<elements-1;i++){
			System.out.print(array[i]+",");
		}
		System.out.print(array[elements-1]);
		System.out.println("]");
	}
}

java数据结构系列之——数组（2）：有序数组