[C/C++ 演算法]-資料結構與演算法(文魁)：插補搜尋使用範例

[C/C++ 演算法]-資料結構與演算法(文魁)：插補搜尋使用範例

 

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php

 

 

 

/* =============== Program Description =============== */
/* 程式名稱 : 5_4.cpp							       */				
/* 程式目的 : 插補搜尋使用範例					       */
/* 輸    入 : 整數陣列資料,要搜尋的鍵值				   */
/* 輸    出 : 整數陣列資料中搜尋鍵值的位置			   */
/* =================================================== */
#define n 9

// 宣告標頭檔
#include "stdio.h"


// 宣告函式原型

// 利用傳位址的方式把Array A傳進search函式中
// 利用傳值的方式把整數key傳進search函式中
int search(int *A,int key);

void main(void)
{
	int A[n]={10,20,30,40,50,60,70,80,90};
	int key,i,ret;

	// 陣列資料的資料
	printf(" Array : ");	
	for(i=0;i<n;i++)
		if(i%6==0)
			printf("\n         A[%2d]=%2d",i,A[i]);	
		else
			printf("A[%2d]=%2d",i,A[i]);	
	printf("\n");	

	// 要搜尋的鍵值	
	key=50;
	printf(" Key   : %d\n",key);	

	// 開始搜尋
	ret = search(A,key);

	// 整數陣列資料中搜尋鍵值的位置
	if(ret!=-1)
		printf(" Index : %d\n",ret);	
	else
		printf(" Key %d is not found ! \n",key);

	getchar();
}

int search(int *A,int key)
{
	int low=0,upper=n-1,mid; 	/*n��陣列宣稱的維數*/
	mid=low+(key-A[low])*(upper-low)/(A[upper]-A[low]);
	if(mid<low)
		mid=low;
	if(mid>upper)
		mid=upper;
	while(low<=upper)
	{
		if(key==A[mid])
			return mid;   /*搜尋成功*/
		else if(key<A[mid])
			upper=mid-1;
		else if(key>A[mid])
			low=mid+1;

		if(low<upper)
			mid=low+(key-A[low])*(upper-low)/(A[upper]-A[low]);
		if(mid<low)
			mid=low;
		if(mid>upper)
			mid=upper;
	}
	return 0;	/*搜尋失敗*/
}