2014年12月24日 星期三

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

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


 


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


  


/* =============== Program Description =============== */
/* 程式名稱 : 5_3.cpp */
/* 程式目的 : 二元搜尋使用範例(前提資料要先排序) */
/* 輸 入 : 整數陣列資料,要搜尋的鍵值 */
/* 輸 出 : 整數陣列資料中搜尋鍵值的位置 */
/* =================================================== */
#define n 9

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


// 宣告函式原型

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

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=70;
printf(" Key : %d\n",key);

// 開始搜尋
ret = binary_search(A,key,0,n-1);

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

getchar();
}

int binary_search(int *A,int key,int low,int upper)
{
int mid=0;

while(low<upper)
{
mid=(int)((low+upper)/2);
if(key==A[mid])
return mid; /* 搜尋成功 */
else if(key>A[mid])
low=mid+1;
else
upper=mid-1;
}
return -1; /* 搜尋失敗 */
}


















 






沒有留言:

張貼留言