作者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/cn.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