查找技术----顺序查找、二分查找


顺序查找:

顺序查找的优缺点:

顺序查找最好的情况为1次,最差的情况为n次,所有查找成功时的平均查找长度为(n+1)/2,且顺序查找的时间复杂度为O(n)

1.在有序的数组中查找数字的下标:

2.利用二分法查找数字的下标:

这种方法前提是在有序的数列中,查找次数可以大大的缩减,内存开辟的次数也可以极大化的减少。增加了运行的速度。

总结:

1、顺序查找使用情况:a、线性表为无序表

            b、表采用链式存储结构

2、二分法查找使用情况:a、适用于顺序存储的有序表

             b、对于长度为n的有序线性表,最坏情况只需比较log2n次

C