作者gna239 ( Kaonashi)
看板C_and_CPP
標題[問題] 二元搜尋法
時間Thu May 14 23:37:38 2009
在一個排完順序後的分數陣列裡
用二元搜尋法來尋找某一個分數在這列中的位置
然後我也要找 這個數字在這個陣列中 是第幾個高分
然後也要找這個分數 在陣列裡面有幾個是同分的
我遇到的問題是....
當重複的分數一多的時候
找到的第幾高分會有錯誤耶
UnSorted numbers :
10 54 84 81 72 39 10 93 64 81 27 10 10 64 10 20 10
Sorted numbers :
10 10 10 10 10 10 20 27 39 54 64 64 72 81 81 84 93
Please enter the score what you want to search:10
The rank of the score is: 14
The number of the score is:6
要從二元搜尋法的程式碼裡來做修正?
還是從找幾個同分的程式碼來做修正?
程式碼有點多 如果需要的話我在PO上來
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.252.6
1F：→ liu2007:PO吧 要註解..... 05/15 00:12
2F：推 VictorTom:先用二分搜尋找到目標分數, 再找頭找尾算幾個一樣的?? 05/15 00:15
3F：→ MOONRAKER:沒錯啊 第14個的確是10啊 05/15 00:16
4F：→ MOONRAKER:二分搜尋只會找一個，他先看到哪一個就是哪一個 05/15 00:17
5F：→ MOONRAKER:你要教他怎麼處理重覆 05/15 00:17
6F：推 netsphere:開個 char score[100]; 把有出現的分數設1 在BS一下 END 05/15 01:07
7F：推 Ebergies:從頭找尾算幾個一樣的都 O(n) 了... 那還需要二分搜尋嗎 05/15 13:24