线性查找与二分查找

1、线性查找

在常规无序数组中，设数组项个数为N，则一个数组项平均查找长度为N/2。极端情况下，查找数据项在数组最后，则需要N步才能找到。

2、二分查找

前提是查找的数组为有序数组。相对于线性查找，待查数组项查找范围越大，体现的查找效率就更为显著。

步数	所猜的数	结果	可能值的范围
0			1~100
1	50	太高	1~49
2	25	太低	26~49
3	37	太高	26~36
4	31	太低	32~36
5	34	太高	32~33
6	32	太低	33~33
7	33	正确	正确

示例代码：

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 {
                        // 如果中间值小于待查找的值，则将查找的最小下限值设为中间值下标+1
                        if (a[curIn] < searchKey) {
                                lowerBound = curIn + 1;
                        // 如果中间值大于待查找的值，则将查找的最大上限值设为中间值下标-1
                        } else {
                                upperBound = curIn - 1;
                        }
                }
        }
}
                

3、大O表示法表示各算法和操作所需的时间

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