文明之精神，野蛮之体魄。
全部博文（64）
分类： C/C++
2013-10-21 19:35:04
一、 顺序表和有序表查找
1. 顺序表查找
从线性表中的第一个（或最后一个）数据元素开始，逐个进行数据元素关键字和给定值的比较，若某个数据元素的关键字和给定值相等则查找成功；如果直到最后一个（或第一个）数据元素，其关键字和给定值都不等时，则查找失败。
2. 代码实现
#include
#include
#include
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define SIZE 20
void print_array(int a[],int begin,int end)
{
int i = 0;
for(i = begin;i < end;i++){
printf("%d, ",a[i]);
}
printf("\n");
}
int another_search(int a[],int len,int key)
{
int ret = len;
a[0] = key;//做为哨兵
while(a[ret] != key){
ret--;
}
return ret;
}
int main(int argc, char *argv[])
{
int a[SIZE+1] = {0};
int i = 0;
int key = 0;
int index = 0;
srand((unsigned int)time(NULL));
for(i = 1;i <= SIZE;i++){
a[i] = rand() % 100;
}
key = rand() % 100;
printf("Another serach demo:\n");
printf("Key: %d\n",key);
printf("Array: \n");
print_array(a,1,SIZE);
index = another_search(a,SIZE,key);
if(index > 0){
printf("Success: a[%d] = %d\n",index,a[index]);
}else{
printf("Failed!\n");
}
}
3. 二分查找
基本思想
首先将查找表进行排序。
取中间数据元素进行比较。
当给定值与中间数据元素的关键字相等时，查找成功。
当给定值小于中间元素时，在中间元素左区间进行二分查找。
当给定值大于中间元素时，在中间元素右区间进行二分查找。
当任意区间均无记录时，查找失败。
4. 二分查找实现
#include
#include
#include
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define SIZE 20
void print_array(int array[],int len)
{
int i = 0;
for(i = 0;i < len;i++){
printf("%d ",array[i]);
}
printf("\n");
}
void swap(int array[],int i,int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void SelectionSort(int array[],int len)
{
int i = 0;
int j = 0;
int k = -1;
for(i = 0;i < len;i++){
k = i;
for(j = i;j < len;j++){
if(array[k] > array[j]){
k = j;
}
}
swap(array,i,k);
}
}
int Binary_search(int a[],int low,int high,int key)//递归
{
int ret = -1;
if(low <= high){
int mid = (low + high) / 2;
if(a[mid] == key){
ret = mid;
}else if(key < a[mid]){
ret = Binary_search(a,low,mid - 1,key);
}else if(key > a[mid]){
ret = Binary_search(a,mid + 1,high,key);
}
}
return ret;
}
int Binary_search_ex(int a[],int low,int high,int key)//用循环代替递归
{
int ret = -1;
while(low <= high){
int mid = (low + high) / 2;
if(a[mid] == key){
ret = mid;
break;
}else if(key < a[mid]){
high = mid - 1;
}else if(key > a[mid]){
low = mid + 1;
}
}
return ret;
}
int main(int argc, char *argv[])
{
int a[SIZE] = {0};
int i = 0;
int key = 0;
int index = 0;
srand((unsigned int)time(NULL));
for(i = 0;i < SIZE;i++){
a[i] = rand() % 100;
}
SelectionSort(a,SIZE);
key = rand() % 100;
printf("Binary serach demo:\n");
printf("Key: %d\n",key);
printf("Array: \n");
print_array(a,SIZE);
index = Binary_search_ex(a,0,SIZE - 1,key);
if(index >= 0){
printf("Success: a[%d] = %d\n",index,a[index]);
}else{
printf("Failed!\n");
}
}
5. 二分查找进一步分析
二分查找的精髓
mid = (low + high) / 2
等量代换：mid = low + (high – low) / 2
扩展：设f(x) = 1/2,则：mid = low + f(x) * (high – low)
问题：如何选择f(x)。
f(x)的选择可以不只是常数，但必须满足：
0 <= f(x) <= 1
由于二分查找基于有序的线性表，因此对于给定的查找值key，我们可以事先估计它的位置。
如：
key = 4
list = {1, 3, 4, 5, 6, 8, 10, 11, 13, 14, 15, 16}
6. 插值查找
根据要查找的关键字key与查找表中的最大最小记录的关键字比较后的查找方法，其核心为：
mid = low + f(key)(high - low).
f(x) = (x – a[low]) / (a[high] – a[low])
7. 插值查找实现
int interpolation_search(int a[],int low,int high,int key)
{
int ret = -1;
while((low <= high) && (a[low] <= key) && (key <= a[high])){
float fx = 1.0f * (key - a[low]) / (a[high] - a[low]);
int mid = low + fx * (high - low);
printf("%d\n",a[mid]);
if(a[mid] == key){
ret = mid;
break;
}else if(key < a[mid]){
high = mid - 1;
}else if(key > a[mid]){
low = mid + 1;
}
}
return ret;
}
8. 小结
顺序查找比较土，但却是其他查找算法的基础。
二分查找基于有序的线性表，时间复杂度提高到O(log n)。
二分查找可以根据需要进一步演变为插值查找。
