查找算法——抽签算法（假如我告诉你：不管多少元素，都只需要比对一次，你信还是不信？）

古城微笑少年丶 2022-09-10 13:22 182阅读 0赞

![请添加图片描述][2199d95f19b94e6a8ca147d44897f63a.png_pic_center]

**抽签算法的基本思想**

抽签是中国的民间习俗，是占卜的其中一种形式。那么可以抽签的形式随机找出序列中的元素进行比对，如果运气足够好，那么不管多少元素，都只需要比对一次，这就是这个算法最神秘之处，用阳寿来查找。

**步骤**

1.  产生一个随机数  r a n d N u m randNum randNum
2.  随机数对数组长度进行取余获取抽中元素的下标  i n d e x = r a n d N u m index=randNum%length index=randNum
3.  与目标元素进行比较，如果不相等，则重复1、2；直至找到

**过程演示**

在序列  \[ 3 , 44 , 38 , 5 , 47 , 15 , 36 , 26 , 1 , 2 \] \[3,44,38,5,47,15,36,26,1,2\] \[3,44,38,5,47,15,36,26,1,2\] 中查找 2

1.  第一种结果：查找 1 次
    
    ![image-20210908195234835][]
2.  第二种结果：查找 18 次
    
    ![image-20210908195513600][]
3.  第三种结果：查找 3 次
    
    ![image-20210908195608947][]

**算法代码**

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    //抽签算法 
    void DrawAlgorithm(int nums[],int num,int n){
    	srand((int)time(0));				//产生随机种子 
    	int count=0,randNum,bound=n*n;		
    	while(true&&count<bound){			//当寻找次数到达 bound 时停止 
    		count++;
    		randNum=rand()%n;				//生成随机数 
    		if(nums[randNum]==num){			
    			break;						//如果找到 num，则 break 退出循环 
    		}
    	}
    	cout<<"已找到 "<<num<<"，寻找次数 count："<<count;
    } 
    
    //打印数组 
    void printNum(int numbers[],int n){
    	for(int i=0;i<n;i++){
    		cout<<numbers[i]<<" ";
    	}
    	cout<<endl; 
    }
    
    int main()
    {
    	int numbers[10]={3,44,38,5,47,15,36,26,1,2};
    	int n=sizeof(numbers)/sizeof(numbers[0]);	//数组长度 
    	cout<<"序列为："; 
    	printNum(numbers,n);		//打印数组 
    	DrawAlgorithm(numbers,2,n);		//调用 DrawAlgorithm 函数在 numbers 序列中进行抽签查找 2 
        return 0;
    }

**算法性能分析**

*  空间复杂度： O ( 1 ) O(1) O(1)
 *  时间复杂度
    
     *  最好情况下时间复杂度： O ( 1 ) O(1) O(1)
     *  最坏情况下时间复杂度：不确定

[2199d95f19b94e6a8ca147d44897f63a.png_pic_center]: /images/20220829/09a90af14d80445f8e181f0b219a7511.png
[image-20210908195234835]: /images/20220829/0ebe046186f14211a21e6ae0e70b73fb.png
[image-20210908195513600]: /images/20220829/63a80bd1af12403490ef2a5339f24db2.png
[image-20210908195608947]: /images/20220829/138c7cfe3f6a42ecbd000a920d6486de.png