作者anoymouse (沒有暱稱)
看板C_and_CPP
標題[問題] binary search 指標參數問題
時間Fri Jun 30 10:44:53 2017
Win10
gcc
goo.gl/Q3ybkG
p145,146
大意就是拿一個字串跟結構陣列裡面的每個字串成員做比較,找到一樣的字串
結構陣列的字串已經是由小到大的排列了
int binsearch(char *word, struct key tab[], int n)
n是陣列大小,在binsearch裡面
low = 0;
high = n - 1;
後來又改成一個指標指到結構版本 p148,149
struct key *low = &tab[0];
struct key *high = &tab[n];
請問為什麼這邊的n就不減一了?
後面寫到
The initializers for low and high are now pointers to the beginning and just
past the end of the table(陣列結尾的下一位)
mid = (low+high)/2 /* WRONG */
because the addition of pointers is illegal. Subtraction is legal, however,
so high-low is the number of elements, and thus
mid = low + (high-low)/2
應該只是說指標不能相加,但是可以相減,雖然第二種也可以避免overflow的問題
但還是不懂為什麼n不減一
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.75.14.196
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1498790695.A.02C.html
※ 編輯: anoymouse (211.75.14.196), 06/30/2017 10:47:47
1F:→ Hazukashiine: 不管是 n 還是 n-1 結果都一樣 只是找中間值附而已 06/30 11:40
2F:→ Hazukashiine: 近 06/30 11:40
3F:→ aiwhat: n 沒減一的後面的 while 有調整成 low < high 06/30 12:33
4F:→ aiwhat: 原本的是 low <= high,做的事情是一樣的 06/30 12:34
5F:→ aiwhat: 只差在一個用 [low, high] 表示搜尋範圍,另一個用 06/30 12:38
6F:→ aiwhat: [low, high)表示 06/30 12:38
7F:→ anoymouse: 所以只是想強調取到陣列範圍外下一個元素是合法的? 06/30 13:05
8F:→ anoymouse: 謝謝兩位回答!! 06/30 13:10
9F:→ Hazukashiine: 指向陣列後面一個元素的指標合法 但存取該指標則否 06/30 14:05
10F:→ anoymouse: 是 書上也有寫到 可以reference 不能dereference 06/30 15:59
11F:→ anoymouse: 謝謝! 06/30 15:59