对择半查找法的改进-----------摇摆查找法

TYCY · 发表于 2010-2-8 20:38:46

// Rock_Search.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
int Rock_Search(int p[],int n,int key,int step);
int Mid_Search(int p[],int n,int key);
#define NUM 100
#define SEARCH1 97
#define SEARCH2 NUM/2
#define SEARCH3 NUM-2
int main(int argc, char* argv[])
{
int data[NUM];
int i;
int result;
for (i=0;i<NUM;i++)
{
data[i] = i;
}
Mid_Search(data,NUM,SEARCH1);
Mid_Search(data,NUM,SEARCH2);
Mid_Search(data,NUM,SEARCH3);
Rock_Search(data,NUM,SEARCH1,10);
Rock_Search(data,NUM,SEARCH2,10);
Rock_Search(data,NUM,SEARCH3,10);
getchar();
return (0);
}
/*
摇摆搜索算法(Rock_Search)【此算法由涂洋写于 2010年2月5号】
P[]:待搜索数组（需要按照从小到大排序，不能不排序或倒序）
n:待搜搜数组的大小
key:待搜索的数据
step:定分点，每次舍弃数组大小的STEP-1/STEP（也就是只保留1/STEP），理论上值越大搜索越快，但也要根据实际情况而定，可先测试
一般搜索的值位于两端时，值越大越好
搜索值位于中间时，值取 N/20 最好
算法说明：
择半搜索法有一个缺陷，对于位于所搜数组两端的数据，搜索的时候效率较低
需要择半到最后一次
并且每次舍弃一半的数据也不算很多
而摇摆算法则完全屏蔽了这个缺点
采用定分点手法取舍，例如
对于 P[0]=0 P[1]=1 ....P[100]=100 这个数组来说，假如要找97这个数据
STEP取10，每次舍弃数组大小的1/10
对于位于两端的数据，舍弃幅度最大
但是位于中间的数据就会应为左右摇摆不定而花费大量时间
所以每次循环的时候检测 odir 和 dir 是否相等，不相等就说明左右摇摆，数据在中间
那么进行一次择半
比如对于1-100这个数据说，49相当靠近中间，所以进行一次择半
那么新的数据就是1-50，这样49对已新数组来说就是极端了，这样对于摇摆算法来说非常有利
*/
int Rock_Search(int p[],int n,int key,int step)
{
int low = 0,high = n-1;
int index = 0;
int dir,odir;
const int right = 1;
const int left = 2;
int n_count = 0;
dir = left;
odir = dir;
if (step > (n/2))
{
return (-2);
}
while (low <= high)
{
n_count++;
if (dir == left)
{
index = low + (high - low + 1)/step;
if (p[index] == key)
{
printf("n_count=%d\n",n_count);
return (index);
}
if (p[index] < key)
{
low = index + 1;
odir = dir;
dir = right;
}
if (p[index] > key)
{
high = index - 1;
odir = dir;
dir = left;
}
}
else if(dir == right)
{
index = high - (high - low + 1)/step;
if (p[index] == key)
{
printf("n_count=%d\n",n_count);
return (index);
}
if (p[index] < key)
{
low = index + 1;
odir = dir;
dir = right;
}
if (p[index] > key)
{
high = index - 1;
odir = dir;
dir = left;
}
}
if (dir != odir)
{
index = (low + high)>>1;
if (p[index] == key)
{
printf("n_count=%d\n",n_count);
return (index);
}
if (p[index] < key)
{
low = index + 1;
}
if (p[index] > key)
{
high = index - 1;
}
}
}
printf("Not Find\n");
return (-1);
}
int Mid_Search(int p[],int n,int key) // 择半搜索法
{
int index,low,high,i;
low = 0;
high = n-1;
int n_count = 0;
while (low<=high)
{
n_count++;
index = (low + high)>>1;
if (p[index] == key)
{
printf("n_count=%d\n",n_count);
return (index);
}
if (p[index] < key)
{
low = index + 1;
}
if (p[index] > key)
{
high = index - 1;
}
}
printf("Not Find\n");
return (-1);
}

复制代码

tonykids · 发表于 2010-2-8 23:39:00

纯支持一下！

murmur · 发表于 2010-2-9 10:44:23

/roll 1-100
你roll出了49点

天啊！正好这是你要查找的数字

TYCY · 发表于 2010-2-9 11:44:13

汗，怎么和ROLL点联系起来了……

Alanwywy · 发表于 2010-2-9 13:29:32

/roll
2499 (!?)

murmur · 发表于 2010-2-9 18:34:45

随机查找法

TYCY · 发表于 2010-2-11 15:01:25

也可以这么说

csh · 发表于 2010-2-15 14:13:24

顶一下好久没见程序讨论帖...

Still4 · 发表于 2010-2-16 03:43:03

理论上讲最快的方法是取黄金分割点查找也就是0.618

TYCY · 发表于 2010-2-16 14:38:54

发现黄金分割的用处很大，用途很广

		自动登录	找回密码
密码			加入易码

对择半查找法的改进-----------摇摆查找法

评分