Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

Binary Search problem

 
Ranch Hand
Posts: 168
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am trying to make a binary search for my array. Sometimes it works fine, other times it prints out the error message, and the different variables i use in my calculation.
I have found that when the error occurs, mid is always one behind the value found at that point in the array.

An example error output:
error
number to find :> 4678 Mid :> 4677 ArrayMid :> 4678 lowerBound :> 4673 upperBound :> 4681

and the search algorithm:
 
Ranch Hand
Posts: 34
Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

tom davies wrote:



Shouldn't this comparison be " if(sortedArray[mid] == numberToFind) " ?
 
Suresh Sajja
Ranch Hand
Posts: 34
Java
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Going beyond your post:

There is a bug in this line

int mid = (lowerBound + upperBound)/2;

It should be

int mid = lowerBound + ((upperBound- lowerBound ) / 2);

Please read more from Google research blog



 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks, that seems to be working for me now. Also an interesting article.
 
He baked a muffin that stole my car! And this tiny ad:
Free, earth friendly heat - from the CodeRanch trailboss
https://www.kickstarter.com/projects/paulwheaton/free-heat
reply
    Bookmark Topic Watch Topic
  • New Topic