有序數組

public class OrderArray {
	private int[] array;
	private int length;//數組元素個數
	//構造方法，傳入數組的最大長度
	public OrderArray(int max){
		array = new int[max];
	}
	//用二分查找定位某個元素，如果存在，傳回其下标，不存在傳回-1
	public int find(int target){
		int left = 0;
		int right = length - 1;
		int mid = 0;
		while(left<=right){
			mid = (left + right)/2;
			if(target<array[mid]){
				right = mid - 1;
			}else if(target>array[mid]){
				left = mid + 1;
			}else{				
				break;
			}
	}
		//跳出循環隻有兩種結果，要麼找到，要麼沒有找到
		if(array[mid] == target){
			return mid;
		}else{
			return -1;
		}
	}	
	//插入:分兩步
	public void insert(int item){
		int location = 0;
		//1:先找到插入的位置,一旦找到位置，必須趕緊退出循環
		for(;location < length;location++){
			if(item<array[location]){
				break;
			}
		}
		//2:然後元素的移動
		for(int index = length;index>location;index--){
			array[index] = array[index-1];
		}
		array[location] = item;
		length++;
	}
	//删除某個元素,删除成功傳回true，删除失敗傳回false               
	public boolean delete(int target){
		int index = -1;
		if((index = find(target))!=-1){
			for(int i = index;i<length -1;i++){
			   array[i] = array[i+1];
		}
		length --;
		return true;
	}else{
		return false;
	}
}
	//列出所有元素
	public void display(){
		for(int i = 0;i<length;i++){
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
	public static void main(String[] args){
		OrderArray orderArray = new OrderArray(10);
		orderArray.insert(3);
		orderArray.insert(4);
		orderArray.insert(7);
		orderArray.insert(5);
		orderArray.insert(6);
		orderArray.insert(2);
		orderArray.display();
		int k = orderArray.find(5);
		System.out.println("該元素的下标是：" + k);
	}
}
           

運作結果：

2 3 4 5 6 7 

該元素的下标是：4

同樣都是二分查找，還可以用下面這種方法：

public int find(int target){
		int left = 0;
		int right = length - 1;
		int mid;
		while(true){
			mid = (left + right)/2;
			if(target == array[mid]){
				return mid;
			}else if(left == mid){
				if(target == array[right]){    //當該搜尋段隻有一個或者兩個元素時，排除了target==array[mid]這種情況
					return right;
				}else{
					return -1;       //該搜尋段沒有目标target元素
				}		
			}else{
				// 搜尋段中的元素至少有三個，且目前元素不等于目标元素
				if(target<array[mid]){
					right = mid - 1;
				}else{
					left = mid + 1;
				}
			}
		}
	}