可用于插入新元素的Binary Search

/**	Java数据结构和算法(第二版)第二章 编程作业
/**	Programming Projects for Chapter 2 Arrays, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
class OrdArray {
	private long[] a; // ref to array a
	private int nElems; // number of data items

	public OrdArray(int max) // constructor
	{
		a = new long[max]; // create array
		nElems = 0;
	}

	public int size() {
		return nElems;
	}

	public void insert(long value) // put element into array
	{
		int j = findIndex(value);
		display();
		for (int k = nElems; k > j; k--)
			// move bigger ones up
			a[k] = a[k - 1];
		a[j] = value; // insert it
		nElems++; // increment size
	}

	public int findIndex(long value) {
		int lowerBound = 0;
		int upperBound = nElems - 1;
		int currentIndex = 0;

		if (nElems == 0) {
			return 0;
		} else if (nElems == 1) {
			if (value > a[0])
				return 1;
			else
				return 0;
		}

		while (true) {
			currentIndex = (lowerBound + upperBound) / 2;
			if (a[currentIndex] == value) {
				return currentIndex;
			} else if (lowerBound == upperBound - 1 || lowerBound==upperBound) {
				if (value < a[lowerBound])
					return lowerBound;
				else
					return upperBound;
			} else if (a[currentIndex] < value) {
				lowerBound = currentIndex + 1;
			} else {
				upperBound = currentIndex - 1;
			}
		}
	}

	public boolean delete(long value) {
		int j = find(value);
		if (j == nElems) // can't find it
			return false;
		else // found it
		{
			for (int k = j; k < nElems; k++)
				// move bigger ones down
				a[k] = a[k + 1];
			nElems--; // decrement size
			return true;
		}
	}

	public void display() // displays array contents
	{
		for (int j = 0; j < nElems; j++)
			// for each element,
			System.out.print(a[j] + " "); // display it
		System.out.println("");
	}

} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注