首页 > 代码库 > 二叉搜索的各种bugs——重复递增序列
二叉搜索的各种bugs——重复递增序列
int binary_search(int* A, int value, int p, int r);int main(int argc, char *argv[]){ int A[] = {1, 2, 3, 4, 4, 4, 4, 4, 4, 5}; int index = binary_search(A, 4, 0, 9); printf("%d\n", index); return 0;}int binary_search(int* A, int value, int p, int r){ if(A==NULL || p>r){ return -1; } int q; while(p<r){ q = p/2 + r/2; if(value=http://www.mamicode.com/=A[q]){ if(A[q] == A[q-1]){ r = q-1; } else{ return q; } } else if(value > A[q]){ p = q+1; } else if(value < A[q]){ r = q-1; } }
return -1;}
1 while(p<r) error case:
查找value 5
q = (p+r)/2 = 4
p = q + 1 = 5
(p < r) != true
while 结束，没有找到5
2 q = p/2 + r/2 error case:
查找value 5
q = p/2 + r/2 = 4
q 超出了p和r的范围，陷入死循环之中
3 q = (p+r)/2 可能会越界
4 A[q] == A[q-1] 可能会越界
正确的方案（忽略 p+r 越界）
int binary_search(int* A, int value, int p, int r){ if(A==NULL || p>r){ return -1; } int q; while(p<=r){ q = (p + r)/2; if(value=http://www.mamicode.com/=A[q]){ if(q>0 && A[q] == A[q-1]){ r = q-1; } else{ return q; } } else if(value > A[q]){ p = q+1; } else if(value < A[q]){ r = q-1; }
二叉搜索的各种bugs——重复递增序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。