《Java数据结构与算法》第2章——数组

假设数组的长度为N，则：

操作	不允许重复	允许重复
查找	N/2次比较	N次比较
插入	无比较，一次移动	无比较，一次移动
删除	N/2次比较，N/2次移动	N次比较，多于N/2次移动

二分查找算法

二分查找所需的比较次数

范围	所需比较次数
10	4
100	7
1000	10
10000	14
100000	17
1000000	20
10000000	24
100000000	27
1000000000	30

示例

package secondchapter;

class OrdArray
{
	private long[] a;
	private int nElems;
	
	public OrdArray(int max)
	{
		a = new long[max];
		nElems = 0;
	}
	
	public int size()
	{
		return nElems;
	}
	
	public int find(long searchKey)
	{
		int lowerBound = 0;
		int upperBound = nElems - 1;
		int curIn;
		
		while (true)
		{
			curIn = (lowerBound + upperBound) / 2;
			if (a[curIn] == searchKey)
				return curIn;
			else if (lowerBound > upperBound)
				return nElems;
			else
			{
				if (a[curIn] < searchKey)
					lowerBound = curIn + 1;
				else
					upperBound = curIn - 1;
			}
		}
	}
	
	public void insert(long value)
	{
		int j;
		for (j=0; j<nElems; j++)
			if (a[j] > value)
				break;
		for (int k=nElems; k>j; k--)
			a[k] = a[k-1];
		a[j] = value;
		nElems++;
	}
	
	public boolean delete(long value)
	{
		int j = find(value);
		if (j == nElems)
			return false;
		else
		{
			for (int k=j; k<nElems; k++)
				a[k] = a[k+1];
			nElems--;
			return true;
		}
	}

    public void display()
	{
		for (int j=0; j<nElems; j++)
			System.out.print(a[j] + " ");
		System.out.println("");
	}
}

public class OrderedApp {

	public static void main(String[] args) {

		int maxSize = 100;
		OrdArray arr = new OrdArray(maxSize);
		
		arr.insert(77);
		arr.insert(99);
		arr.insert(44);
		arr.insert(55);
		arr.insert(22);
		arr.insert(88);
		arr.insert(11);
		arr.insert(00);
		arr.insert(66);
		arr.insert(33);
		
		int searchKey = 55;
		if (arr.find(searchKey) != arr.size())
			System.out.println("Found " + searchKey);
		else
			System.out.println("Can't find " + searchKey);
		
		arr.display();
		
		arr.delete(00);
		arr.delete(55);
		arr.delete(99);
		
		arr.display();
	}
}

结果：
Found 55
0 11 22 33 44 55 66 77 88 99
11 22 33 44 66 77 88

用大O表示法表示运行时间

算法	大O表示法表示的运行时间
线性查找	O(N)
二分查找	O(logN)
无序数组的插入	O(1)
有序数组的插入	O(N)
无序数组的删除	O(N)
有序数组的删除	O(N)