KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Binary search can be implemented in many ways-recursive, iterative, conditionals, etc. I took this from Bentley's book " Programming pearls : Writing correct programs" which is an iterative implementation, and that includes a bug. public class BinSearch { static int search( int [] A, int K ) { int l = 0; int u = A. length -1; int m; while ( l <= u ) { m = (l+u) /2; if (A[m] < K){ l = m + 1; } else if (A[m] == K){ return m; } else { u = m-1; } } return -1; } } I found a bug in the line m = (l+u) /2; it can lead to overflow. How can we avoid this overflow in this binary search?
Tags (comma-separated)
Save Edits
Cancel