package ArrayDemo;

public class HighArray {
	
	private int[] arr = null;
	private int nElement = 0;//当前数组的实际长度
	public HighArray(int size){
		this.arr = new int[size];
		this.nElement = 0;
	}
	
	/**查找指定元素是否在数组中存在，返回结果
	 * @param c
	 * @return
	 */
	public boolean find(int c){
		int i;
		for ( i = 0; i < nElement && arr[i]!=c; i++);
		return i != nElement;
	}
	
	/**插入
	 * @param c
	 */
	public void insert(int c){
		arr[nElement++] = c;
	}
	
	/**删除
	 * @param c
	 * @return
	 */
	public boolean delete(int c){
		int i;
		for ( i = 0; i < nElement && arr[i]!=c; i++);
		if(i!=nElement){
			nElement--;
			for (int j = i; j < nElement; j++) {
				arr[j] = arr[j+1];
			}
			return true;
		}else{
			return false;
		}
	}
	
	/**获取当前最大元素
	 * @return
	 */
	public int getMax(){
		if(nElement > 0){
			int max = arr[0];
			for (int i = 1; i < nElement; i++) {
				if(arr[i] > max)max = arr[i];
			}
			return max;
		}
		return -1;
	}
	
	/**删除并且返回最大元素
	 * @return
	 */
	public int removeMax(){
		if(nElement > 0){
			int max = arr[0];
			for (int i = 1; i < nElement; i++) {
				if(arr[i] > max)max = arr[i];
			}
			delete(max);
			return max;
		}
		return -1;
	}
	
	public void display(){
		for (int i = 0; i <nElement; i++) {
			System.out.println(arr[i]);
		}
	}
	
	/**
	 * 删除数组中存在的重复元素并缩小数组长度
	 */
	public void noDup(){
		int count  = 0;
		for (int i = 0; i < nElement; i++) {
			if(arr[i] != -1){// -1为空值的表现
				for (int j = 0; j < nElement; j++) {
					if(i!=j && arr[i] == arr[j]){
						arr[j] = -1;
						count++;
					}
				}
			}
			
		}
		if(count > 0){
			int j = 0;
			for (int i = 0; i < nElement; i++) {
				if(arr[i]!=-1){
					arr[j++] = arr[i];
				}
			}
			for (int k = j; k < nElement; k++) {
				arr[k] = 0;
			}
		}
	
		nElement-=count;
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HighArray h = new HighArray(100);
			h.insert(7);
			h.insert(74);
			h.insert(74);
			h.insert(74);
			h.insert(89);
			h.insert(12);
			h.insert(8);
			h.noDup();
			h.display();
		//	h.delete(12);
			
	}
	
	
}

?

?上面是对一个无序数组做了一些封装和扩展。实现起来稍微简单点。下面介绍下有序数组的二分查找法。

?要实现二分查找法数组必须先满足两个条件1.必须采用顺序存储结构?2.必须按关键字大小有序排列。

二分查找法的基本原理就是：逐渐缩小查询范围，直到查找到元素或者查找不到此元素。它的优点是查找次数较线性查找（也就是按顺序查找所有元素）要高，而且当数组越大时查找次数的优势较线性查找越明显。下面是它查找不同数据量所需要的次数

?怎么样，是不是数据量越大查找次数的优势就越大，比如在10000里查找一个元素，线性查找需要的平均次数是1000/2 = 5000次， 而二分查找法的计算公式是以二为基数的对数 ，所谓对数就是指数的反函数 ，一般计算器的log函数就是以10为基数的对数，那么计算10000的二分查找法所需次数的公式就是log(10000) * 3.322 ，乘以3.322是因为要将该结果从10的基数转换成2的基数，这样下来四舍五入差不多就是所需次数了。结果是 13.288 取整就是14次。5000比14可想而知效率高了多少。ps:也可以这样计算log2(x) = log(x) / log(2)?

?

?

下面是二分法查找的基本步骤（假如是数组元素升序排序的）

1.将需查找元素和数组中间的元素比较，如果相等则返回，如果数组中间元素比需查找元素大则说明目标元素的位置在中间元素的前面，反之在后面。

2.通过步骤1，已经缩小了一半的范围，然后重复步骤1，直到找到元素或者找不到元素为止，就算找不到也最多就是查找Math.ceil(log(数据长度）* 3.322 )次。

?

?

这有点象我们平常的猜数游戏

java代码二分法实现?

?

public int bianrySearch(int[] arr,int searchKey){
		int lowerBound = 0, upperBound = arr.length - 1;
		while(lowerBound <= upperBound){
			int curIn = (lowerBound + upperBound)/2;
			if(arr[curIn] == searchKey){
				return curIn;
			}else if(arr[curIn] > searchKey){
				upperBound = curIn - 1;
			}else{
				lowerBound = curIn + 1;
			}
		}
		return  src.length;
	}

package ArrayDemo;

public class OrderArray {
	private int[] arr = null;
	private int nElement = 0;
	public OrderArray(int size){
		this.arr = new int[size];
		this.nElement = 0;
	}
	
	public int find(int c){
		int lowerBound = 0, upperBound = nElement - 1;
		while(lowerBound <= upperBound){
			int middle = (lowerBound + upperBound)/2;
			if(arr[middle] == c){
				return middle;
			}else if(arr[middle] > c){
				upperBound = middle - 1;
			}else{
				lowerBound = middle + 1;
			}
		}
		return nElement;
	}
		
	private int doSearchRecursive(int lower,int upper,int c){
		while(lower <= upper){
			int middle = (lower + upper)/2;
			if(arr[middle]==c){
				return middle;
			}else if(arr[middle] < c){
				return doSearchRecursive(middle + 1, upper, c);
			}else{
				return doSearchRecursive(lower, middle -1, c);
			}
		}
		return nElement;
	}
	
	
	/**二分法递归实现
	 * @param c
	 * @return
	 */
	public int findRecursive(int c){
		return doSearchRecursive(0,arr.length - 1,c);
	}

	public void insert(int c){
		int lowerBound = 0,upperBound = nElement -1,max = nElement;
		while(lowerBound <= upperBound ){//用二分法查找在数组中第一个比c大的元素
			int middle = (lowerBound + upperBound)/2;
			if(arr[middle] == c){
				max = middle;
				break;
			}else if(arr[middle] > c){
				max = middle;
				upperBound = middle - 1;
			}else{
				lowerBound = middle + 1;
			}
		}
		//移动数组
		for (int i = nElement; i > max; i--) {
			arr[i] = arr[i - 1];
		}
		arr[max] = c;
		nElement++;
	}
	
	/**将两个有序的数组合并成一个有序的数组
	 * @param src1 
	 * @param src2
	 */
	public void mearge(int[] src1,int[] src2){
		int[] tar = new int[src1.length + src2.length];
		for (int i = 0,k=0,j=0; i < tar.length; i++) {
			if(j >= src2.length || (k < src1.length && src1[k] < src2[j])){
				tar[i] = src1[k++];
			}else{
				tar[i] = src2[j++];
			}
		}
		for (int i = 0; i < tar.length; i++) {
			System.out.println(tar[i]);
		}
		
	}
	public boolean delete(int c){
		int index = find(c);
		if(index != nElement--){
			for (int i = index; i < nElement; i++) {
				arr[i] = arr[i + 1];
			}
			return true;
		}else{
			return false;
		}
	}
	
	public int[] getArr(){
		return this.arr;
	}
	public void display(){
		for (int i = 0; i <nElement; i++) {
			System.out.println(arr[i]);
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		OrderArray h1 = new OrderArray(12);
		for (int i = 0; i < 12; i++) {
			h1.insert((int)(Math.random() * 1000));
		}
	//	h1.display();
		OrderArray h2 = new OrderArray(10);
		for (int i = 0; i < 10; i++) {
			h2.insert((int)(Math.random() * 1000));
		}
		h1.mearge(h1.getArr(), h2.getArr());
	//	System.out.println(h.find(34));
	}
	
}