顺序查找和折半查找

 

                 顺序查找和折半查找

1、顺序表查找：

算法思路：设给定值K,在表（R1...Rn）中，从Rn开始，查找Key=K的记录。若存在一个记录Ri（1<=i<=n）的Key为K,则查找成功，返回记录序号i；否则，查找失败，返回0。平均查找长度ASL = O(n)。

代码如下：

/*顺序结构体存储*/

#include "stdio.h"

#include "assert.h"

#include "strings.h"

#include "stdlib.h"

typedef int int_32;

#define MAXSIZE 10

#define TRUE 1

#define FALSE -1

typedef struct node

{

       int_32 data[MAXSIZE];

       int last;

}sqlist,*sqlink;

void creat_sqlist(sqlink *sq)

{

       *sq = (sqlink)malloc(sizeof(sqlist));

       assert(*sq);

       bzero(*sq,sizeof(sqlist));

       (*sq)->last = 0;

}

int full_sqlist(sqlink sq)

{

       return sq->last == MAXSIZE ? TRUE : FALSE;

}

int length_sqlist(sqlink sq)

{

       return sq->last;

}

int in_sqlist(sqlink sq, int_32 x)

{

       if(full_sqlist(sq) == TRUE)

       {

              printf("sqlist is full!\n");

              return FALSE;

       }

       sq->data[sq->last] = x;

       sq->last++;

       return TRUE;

}

/*顺序查找*/

void sequ_search_sqlist(sqlink sq, int_32 x)

{

       int i = 0;

       for(i; i < length_sqlist(sq); i++)

       {

              if(x == sq->data[i])

              {

                     printf("The number = %d has been found in number %d!\n",x,i+1);

                     return ;

              }

             

       }

       printf("The number = %d has not been found!\n",x);

}

/*折半查找*/

void bin_search_sqlist(sqlink sq, int len, int_32 key)

{

       int low = 0, high = len-1;

       int mid;

       while(low <= high)

       {

              mid = (low + high) / 2;

              if(sq->data[mid] < key)

                     low = mid + 1;

              if(sq->data[mid] > key)

                     high = mid - 1;

              if(sq->data[mid] == key)

              {

                     printf("The key = %d has been found in number %d!\n",key,mid+1);

                     return;

              }

       }

       printf("The key = %d has not been found!\n",key);

}

void display_sqlist(sqlink sq)

{

       int i;

       for(i = 0; i < length_sqlist(sq); i++)

       {

              printf("%d  ",sq->data[i]);

       }

       putchar('\n');

}

int main()

{

       int_32 i = 1;

       sqlink sq = NULL;

       creat_sqlist(&sq);

       while(i<=5)

       {

              in_sqlist(sq,2*i+1);

              i++;

       }

       display_sqlist(sq);

       sequ_search_sqlist(sq,7);

       sequ_search_sqlist(sq,6);

       bin_search_sqlist(sq, length_sqlist(sq), 7);

       bin_search_sqlist(sq, length_sqlist(sq), 6);

       return 0;

}

2、折半查找

算法思路：对给定的值K，逐步确定待查记录所在区间，每次讲搜索空间减少一半（折半），直到查找成功或者失败为止。

设两个指针（或游标）low、high，分别指向当前待查找表的上限（表头）和下限（表尾）。对于表（R1 R2......Rn），初始时low=1、high=n，令：，mid = （low+high）/2。平均查找长度ASL = O(log2(n+1)),大大优于O（n）。

代码如上。