(C/C++学习)11.随机数组的快速查找

说明：利用随机函数生成一个随机数组，然后对数组进行排列，再利用二分查找快速查找一个数。

一.生成随机数组

  1     time_t   ts;
  2     //等价于long ts;
  3     unsigned int num = time(&ts);
  4     srand(num);
  5     int a[10] = {0};
  6     for(int i = 0;i<10;i++)
  7         a[i] = rand()%100;

注意：sizeof(long) = sizeof(unsigned int) = sizeof(time_t) = 4。上述代码也可以用以下代码代替：

  1     srand(time(NULL));
  2     int a[10] = {0};
  3     for(int  i = 0;i<10;i++)
  4         a[i] = rand()%100;

二.对数组进行排列

在上一节已经叙述过快速排序的原理了，这里不再过多讲解，直接上迭代法排序代码。

  1 void sortlist(int *p,int low,int high)
  2 {
  3     if(low < high)
  4     {
  5         int l = low;
  6         int h = high;
  7         int middle = p[low];
  8         while(l<h)
  9         {
 10             while(p[h] >= middle && l<h)
 11                 h--;
 12             p[l] = p[h];
 13             while(p[l] <= middle && l<h)
 14                 l++;
 15             p[h] = p[l];
 16         }
 17         p[h]  = middle;
 18         sortlist(p,low,h-1);
 19         sortlist(p,h+1,high);
 20     }
 21 }

其中 p 为数组名，LOW为 0 ，high为数组元素个数减 1。

三.二分法快速查找

二分法查找适用于查找数据量相当大的数据库，且要求数据有序。假如对于一个有一千个数的有序数组，利用二分法查找一个数据，第一次即可筛选掉500个数据，第二次即可筛选掉250个数据，以此类推。其代码实现如下：

  1 int binarysearch(int *p,int low,int high,int data)
  2 {
  3     if(low <= high)
  4     {
  5         int middle = (low + high)/2;
  6         if(data == p[middle])
  7         {
  8             int midh = middle;
  9             int midl = middle;
 10             while(p[++midh] == data)
 11                 printf("%d %d\n",midh,p[midh]);
 12              while(p[--midl] == data)
 13                  printf("%d %d\n",midl,p[midl]);
 14             return middle;
 15         }
 16         else if(data > p[middle])
 17             return binarysearch(p,middle+1,high,data);
 18         else
 19             return binarysearch(p,low,middle-1,data);
 20     }
 21     return -1;
 22 }

四.最后上一个示例，代码功能是生成一个随机数组，对其采用迭代法进行排序，然后利用二分法查找一个数据。

  1 #include<stdio.h>
  2 #include<time.h>
  3 #include<stdlib.h>
  4 void travelllist(int *p,int n)
  5 {
  6     int i = 0;
  7     for(;i<n;i++)
  8         printf("%d ",p[i]);
  9     putchar(10);
 10 }
 11 
 12 void sortlist(int *p,int low,int high)
 13 {
 14     if(low < high)
 15     {
 16         int l = low;
 17         int h = high;
 18         int middle = p[low];
 19         while(l<h)
 20         {
 21             while(p[h] >= middle && l<h)
 22                 h--;
 23             p[l] = p[h];
 24             while(p[l] <= middle && l<h)
 25                 l++;
 26             p[h] = p[l];
 27         }
 28         p[h]  = middle;
 29         sortlist(p,low,h-1);
 30         sortlist(p,h+1,high);
 31     }
 32 }
 33 
 34 int binarysearch(int *p,int low,int high,int data)
 35 {
 36     if(low <= high)
 37     {
 38         int middle = (low + high)/2;
 39         if(data == p[middle])
 40         {
 41             int midh = middle;
 42             int midl = middle;
 43             while(p[++midh] == data)
 44                 printf("%d %d\n",midh,p[midh]);
 45              while(p[--midl] == data)
 46                  printf("%d %d\n",midl,p[midl]);
 47             return middle;
 48         }
 49         else if(data > p[middle])
 50             return binarysearch(p,middle+1,high,data);
 51         else
 52             return binarysearch(p,low,middle-1,data);
 53     }
 54     return -1;
 55 }
 56 
 57 int main()
 58 {
 59     int i;
 60     srand(time(NULL));
 61     int arr[100] = {0};
 62     for( i = 0;i<100;i++)
 63         arr[i] = rand() % 100;
 64     travelllist(arr,100);
 65     sortlist(arr,0,99);
 66     travelllist(arr,100);
 67     int data = binarysearch(arr,0,99,3);
 68     if(data >= 0)
 69         printf("%d %d",data,arr[data]);
 70     else
 71         printf("find nothing!!");
 72     return 0;
 73 }
 74

查看代码

(C/C++学习)11.随机数组的快速查找

推荐阅读