The Artima Developer Community
Sponsored Link

Agile Buzz Forum
Binary Search Bug

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
James Robertson

Posts: 29924
Nickname: jarober61
Registered: Jun, 2003

David Buck, Smalltalker at large
Binary Search Bug Posted: Jun 3, 2006 2:58 PM
Reply to this message Reply

This post originated from an RSS feed registered with Agile Buzz by James Robertson.
Original Post: Binary Search Bug
Feed Title: Cincom Smalltalk Blog - Smalltalk with Rants
Feed URL: http://www.cincomsmalltalk.com/rssBlog/rssBlogView.xml
Feed Description: James Robertson comments on Cincom Smalltalk, the Smalltalk development community, and IT trends and issues in general.
Latest Agile Buzz Posts
Latest Agile Buzz Posts by James Robertson
Latest Posts From Cincom Smalltalk Blog - Smalltalk with Rants

Advertisement

This is interesting - the "stock" binary search algorithm fails (for the mainstream statically typed languages):

 
1:     public static int binarySearch(int[] a, int key) {


2: int low = 0;

3: int high = a.length - 1;

4:

5: while (low <= high) {

6: int mid = (low + high) / 2;

7: int midVal = a[mid];

8:

9: if (midVal < key)

10: low = mid + 1;

11: else if (midVal > key)

12: high = mid - 1;

13: else

14: return mid; // key found

15: }

16: return -(low + 1); // key not found.

17: }

Line 6 causes problems if (low + high) overflows the size of an int. This is a non-problem in Smalltalk, of course; you seamlessly get large integers and everything "just works". I found the fixes amusing; they are all ways of coding around the limits of the type system.

Read: Binary Search Bug

Topic: Channeling Bill Lyons Previous Topic   Next Topic Topic: Piracy is killing the RIAA!

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use