第48课 - 顺序表和有序表查找
1. 顺序表查找
从线性表中的第一个（或最后一个）数据元素开始，逐个进行数据元素关键字和给定值的比较，若某个数据元素的关键字和给定值相等则查找成功；如果直到最后一个（或第一个）数据元素，其关键字和给定值都不等时，则查找失败。
2. 二分查找
基本思想。
首先将查找表进行排序。
取中间数据元素进行比较。
当给定值与中间数据元素的关键字相等时，查找成功。
当给定值小于中间元素时，在中间元素左区间进行二分查找。
当给定值大于中间元素时，在中间元素右区间进行二分查找。
当任意区间均无记录时，查找失败。
3. 二分查找进一步分析
(1) 二分查找的精髓：mid = (low + high) / 2
(2) 等量代换：mid = low + (high - low) / 2
(3) 扩展：设f(x) = ½，则：mid = low + f(x)(high - low)
(4) f(x)的选择可以不只是常数，但必须满足：0 <= f(x) <= 1。
(5) 由于二分查找基于有序的线性表，因此对给定的查找值key，我们可以事先估计它的位置。
如：
key = 4
list = {1, 3, 4, 5, 6, 8, 10, 11, 13, 14, 15, 16}
4. 插值查找
根据要查找的关键字key与查找表中最大最小记录的关键字比较
后的查找方法，其核心为：
mid = low + f(key)(high - low)
f(x) = (x - a[low]) / (a[high] - a[low])
不同的f(x)的选取可以得到不同的查找算法。
5. 程序
OrderSearch.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void println(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf(" ");
}
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) // O(n*n)
{
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[j] < array[k] )
{
k = j;
}
}
swap(array, i, k);
}
}
int binary_search(int a[], int low, int high, int key) // O(logn)
{
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) // O(logn)
{
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 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);
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=1; i<=SIZE; i++)
{
a[i] = rand() % 100;
}
key = 50;
printf("Binary Search Demo ");
printf("Key: %d ", key);
printf("Array: ");
SelectionSort(a, SIZE);
println(a, SIZE);
index = interpolation_search(a, 0, SIZE-1, key);
if( index > 0 )
{
printf("Success: a[%d] = %d ", index, a[index]);
}
else
{
printf("Failed! ");
}
return 0;
}
AnotherSearch.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void print_array(int a[], int begin, int end)
{
int i = 0;
for(i=begin; i<=end; i++)
{
printf("%d, ", a[i]);
}
printf(" ");
}
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 Search Demo ");
printf("Key: %d ", key);
printf("Array: ");
print_array(a, 1, SIZE);
index = another_search(a, SIZE, key);
if( index > 0 )
{
printf("Success: a[%d] = %d ", index, a[index]);
}
else
{
printf("Failed! ");
}
return 0;
}