秩序配列と二分検索



//OrderArray.java
public class OrderArray {
	private int[] a;

	private int nElements;

	public OrderArray(int max) {
		a = new int[max];
		nElements = 0;
	}

	public void insert(int element) {
		if (nElements == a.length) {
			System.out.println("can't insert, array is full.");
			return;
		}
		int j;
		for (j = 0; j < nElements; j++)
			if (a[j] > element)
				break;
		int k;
		for (k = nElements; k > j; k--)
			a[k] = a[k - 1];
		a[j] = element;
		nElements++;
	}

	/**
	 *  
	 * 
	 * @param element
	 * @return
	 */
	public int binarySearch(int element) {
		int lowerBound = 0;
		int upperBound = nElements - 1;
		int binaryBound;
		while (true) {
			binaryBound = (lowerBound + upperBound) / 2;
			if (a[binaryBound] == element) //  
				return binaryBound;
			else if (lowerBound > upperBound) // 404
				return -1;
			else if (a[binaryBound] > element)
				upperBound = binaryBound - 1;//  
			else
				lowerBound = binaryBound + 1;//  
		}
	}

	public boolean delete(int element) {
		int j = binarySearch(element);
		if (j == -1)
			return false;
		int k;
		for (k = j; k < nElements - 1; k++)
			a[k] = a[k + 1];
		a[nElements - 1] = 0;
		nElements--;
		return true;
	}

	public void display() {
		StringBuffer sb = new StringBuffer();
		sb.append("[");
		int j;
		for (j = 0; j < a.length; j++) {
			sb.append(a[j] + ",");
		}
		sb.deleteCharAt(sb.length() - 1);
		sb.append("]");
		System.out.println(sb.toString());
	}
}

//Main.java
public class Main {
	public static void main(String[] args){
		OrderArray orderArray = new OrderArray(10);
		orderArray.insert(111);
		orderArray.insert(888);
		orderArray.insert(333);
		orderArray.insert(222);
		orderArray.insert(666);
		orderArray.insert(555);
		orderArray.insert(444);
		orderArray.insert(999);
		orderArray.insert(777);
		orderArray.insert(1111);
		orderArray.insert(2222);
		orderArray.display();
		System.out.println(orderArray.binarySearch(88));
		System.out.println(orderArray.binarySearch(1000));
		System.out.println(orderArray.delete(333));
		System.out.println(orderArray.binarySearch(999));
		System.out.println(orderArray.delete(555));
		orderArray.insert(555);
		orderArray.insert(555);
		orderArray.display();
	}
}

出力結果:

can't insert, array is full.
[111,222,333,444,555,666,777,888,999,1111]
-1
-1
true
7
true
[111,222,444,555,555,666,777,888,999,1111]