牽著老婆滿街逛

嚴以律己,寬以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

統計

隨筆 - 1513
文章 - 45
評論 - 907
引用 - 0

公告

言論：
1.每日自省；
2.享受人生；
3.盡力而為；
4.堅持不懈；
5.切莫急躁；
6.慎言敏行；
7.動心忍性；
8.上善若水。

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

搜索

積分與排名

積分 - 2533323
排名 - 2

閱讀排行榜

折半查找(二分查找)

最基本的算法:

int BinarySearch(int arr[], int len, int searchKey)

{

int start = 0, end = len - 1, mid;

while (start <= end)

{

// 求中間的索引值

mid = (start + end) / 2;

if (arr[mid] == number)

{

// 查到了

return mid;

}

else if (arr[mid] < searchKey)

{

// 搜索范圍縮小到后半部

start = mid + 1;

}

else if (arr[mid] > searchKey)

{

// 搜索范圍縮小到前半部

end = mid - 1;

}

// 沒查到

return -1;

}

用到遞歸的算法:

int BinarySearch( const int arr[], int searchKey, int start, int end )

{

// 求中間的索引值

int mid = ( start + end ) / 2;

if ( searchKey == arr[ mid ] )

{

// 找到了

return mid;

}

else if ( searchKey < arr[ mid ] )

{

// 搜索范圍縮小到前半部

return BinarySearch( arr, searchKey, start, mid - 1 );

}

else if ( searchKey > arr[ mid ] )

{

// 搜索范圍縮小到后半部

return BinarySearch( arr, searchKey, mid + 1, end );

}

else

{

// 沒有查找到

return -1;

}

使用迭代實現:

int BinarySearch( const int arr[], const int& len, const int& searchKey )

{

int start=0, end=len-1, mid;

while ( start < end )

{

mid = (start + end) / 2;

if ( searchKey > arr[mid] )

{

start = mid + 1;

}

else

{

end = mid;

}

if ( start > end )

{

return -1;

}

else

{

if ( searchKey == arr[start] )

{

return start;

}

else

{

return -1;

}

測試代碼:

void testBinarySearch()

{

const int LEN = 8;

int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };

printf("查找到的索引號為:%d\n", BinarySearch(a, LEN, 5));

printf("查找到的索引號為:%d\n", BinarySearch(a, 5, 0, LEN-1));

}

posted on 2010-06-02 23:21 楊粼波閱讀(604) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

牽著老婆滿街逛

導航

統計

公告

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

工具官網

技術網站

開源網站

其他窩點

收藏網站

銀行官網

友情鏈接

資源共享

搜索

積分與排名

最新評論

閱讀排行榜

折半查找(二分查找)