Exactly. And note that if pointers and unsigned integers have the same number of bits, overflow can't be a problem as long as the array elements are 2 bytes or more long. I.e. if you have an n-bit machine, the last 2-byte array element can't have index more than 2^n/2 - 1 = 2^(n-1) - 1. Consequently when doing the addition in (lo+hi)/2, the numerator can't be more than 2*[2^(n-1)-1] = 2^n - 2, which isn't an overflow, though you do have to be careful to use unsigned arithmetic in this case.
On Jan 9, 4:48 pm, Don <dondod...@gmail.com> wrote: > The intermediate value of start+end may be too large to store in an > integer, even though start and end by themselves are in the valid > range. If you know this to not be the case, you can use the simpler > form. > Don > > On Jan 8, 5:04 am, Sanjay Rajpal <srn...@gmail.com> wrote: > > > > > In binary search, > > > mid = start + (end-start)/2 is used to avoid overflow, as said by a book. > > > why can't we use mid = (start + end)/2, it says this statement may result > > in overflow ? > > * > > Sanjay Kumar > > B.Tech Final Year > > Department of Computer Engineering > > National Institute of Technology Kurukshetra > > Kurukshetra - 136119 > > Haryana, India > > Contact: +91-8053566286 > > * -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
