Tag Archives: 二分查找

数据结构重读 – 顺序和二分查找、最/次优查找树、索引顺序表查找

概念明天补上。。。

顺序查找,用了哨兵减少检查数组长度的次数,据说这样可以让顺序查找的性能提升一倍

优点:无序任何假设条件(如数组有序等)。

缺点:效率低。
#include <stdio.h>

int ssearch(int* arr, int n, int key)
{
int i = 0;
arr[n] = key;
for(i=0;arr[i]!=key;i++);
if(i==n)
{[……]

继续阅读

算法技术手册 – 查找 – 二分查找

二分查找,要求集合是有序的,在这个条件基础上,它比顺序查找具有更好的性能。

如果使用伴随数组,只需要struct中有一个key是有序的就行。

需要指出的是,当数组放在磁盘上时,时间复杂度就不再是O(LogN),而取决于磁盘存取的开销。

源代码:
#include <stdio.h>

typedef int TYPE;

int search(TYPE* arr, int n, int t)
{
int low = 0;
int hi[……]

继续阅读