• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Confused about binary search algorithm  RSS feed

 
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This was my initial question:

I am confused as to why this won't return the desired value. I keep running into an infinite loop or data is returned that I searched.


This question is updated to latest post of code which is below.

I need help with one question.......

I still need to work on whether a user enters a search that doesn't exist......that is where I am stuck....



code has been updated......
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:I am confused as to why this won't return the desired value. I understand that I also need to include if it doesn't find an element that matches but at the moment I am trying to find an element that matches first.


Well, first up: Is the list sorted? Because it certainly won't work if it isn't.
Second: What's going to happen when you actually find the value (or indeed, if you don't)? Try and work it out on paper.

Winston
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Charles Sexton wrote:I am confused as to why this won't return the desired value. I understand that I also need to include if it doesn't find an element that matches but at the moment I am trying to find an element that matches first.


Well, first up: Is the list sorted? Because it certainly won't work if it isn't.
Second: What's going to happen when you actually find the value (or indeed, if you don't)? Try and work it out on paper.

Winston



It is sorted....insertion sort!
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
binary search is in insertion sort order(ascending and alphabetically);
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
edited:

inefficient code....see code below
 
lowercase baba
Posts: 12628
50
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So put in a bunch of System.out.println() statements to see what your code is really doing.
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:So put in a bunch of System.out.println() statements to see what your code is really doing.



tried that already, but will be doing more......
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
removed
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have this much of the work done......I still need to work on whether a user enters a search that doesn't exist......that is where I am stuck.....






This much of the code worked on is done;

The code below will only find the exact value entered by the user; Binary search algorithm.....
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
removed
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:The code below will only find the exact value entered by the user...


Will it? You've solved half of the problem I posted above; but what happens when it doesn't find the thing you're searching for?

Hint: Most binary chops don't return 'the value'; they return an index.

Winston

PS: You also have another error in your program, but it's quite subtle (so subtle, in fact, that it went undiscovered by the inventors for nearly ten years ). What is the result of 'low + high'?
 
Marshal
Posts: 61756
193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:removed

Don't

That makes replies look like nonsense.
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Charles Sexton wrote:The code below will only find the exact value entered by the user...


Will it? You've solved half of the problem I posted above; but what happens when it doesn't find the thing you're searching for?

Hint: Most binary chops don't return 'the value'; they return an index.



I can see that the runs faster if they return an index. Their is a lot less if statements and checks while looping, which speeds the process up.....but you can do it without indexes but I do see why they are more common with indexes
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Charles Sexton wrote:removed

Don't

That makes replies look like nonsense.



Won't do it again.....thank you for the info......
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

PS: You also have another error in your program, but it's quite subtle (so subtle, in fact, that it went undiscovered by the inventors for nearly ten years ). What is the result of 'low + high'?





This line of code is easily determined by what iteration of the while loop you are in. Mid of an array with 5 elements while looping the first time is 2. The second and third iteration depends on the if statements.....
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:This line of code is easily determined by what iteration of the while loop you are in.


I understand what it does; I'm saying it contains an error. What is the result of (1000000000 + 2000000000)?
Hint: Integer.MAX_VALUE = 2147483647.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:I can see that the runs faster if they return an index.


It's not just that. I ask again: what does your method do if it DOESN'T find the value?

Winston
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Charles Sexton wrote:This line of code is easily determined by what iteration of the while loop you are in.


I understand what it does; I'm saying it contains an error. What is the result of (1000000000 + 2000000000)?
Hint: Integer.MAX_VALUE = 2147483647.

Winston



Oh I see what you mean now......
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:

Winston Gutkowski wrote:

Charles Sexton wrote:This line of code is easily determined by what iteration of the while loop you are in.


I understand what it does; I'm saying it contains an error. What is the result of (1000000000 + 2000000000)?
Hint: Integer.MAX_VALUE = 2147483647.

Winston



Oh I see what you mean now......



I modified it to return a string that says user doesn't exist.....
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:

Charles Sexton wrote:

Winston Gutkowski wrote:

Charles Sexton wrote:This line of code is easily determined by what iteration of the while loop you are in.


I understand what it does; I'm saying it contains an error. What is the result of (1000000000 + 2000000000)?
Hint: Integer.MAX_VALUE = 2147483647.

Winston



Oh I see what you mean now......



I modified my code to return a string that says user doesn't exist.....

 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:This line of code is easily determined by what iteration of the while loop you are in
I understand what it does; I'm saying it contains an error. What is the result of (1000000000 + 2000000000)?
Hint: Integer.MAX_VALUE = 2147483647.

Winston



Oh I see what you mean now......

I modified my code to return a string that says user doesn't exist.....but my algorithm is extremely slow compared to returning an index just like compareTo for String class......
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Charles Sexton wrote:I can see that the runs faster if they return an index.


It's not just that. I ask again: what does your method do if it DOESN'T find the value?

Winston



what if mid is not == to what I am searching for and mid is equal to (low+high)/2

so I need to add some or statements in one of my ifs.....

code updated below and problem is solved.....Took some long hours but the gratification of finishing is far more better.......

Just want to say thanks to Campbell, Winston and Fred.....one day I will be helping others just as y'all have..... +1 to all three


This is for future reference:
It is better as stated above by Winston to return an index instead of comparing a string.....An index being returned would be something similar to compareTo method within the String class


code that works.....but does not work if mid or high is ever greater than maximum size of int.....which is 2,147,483,647.......see Winston's reply above for additional details......
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:code that works.....but does not work if mid or high is ever greater than maximum size of int....


Well done.

And just FYI, there are two ways of solving that problem that will work if high and low are always 0 or positive (which is normal for an index):
1. mid = low + ((high - low) / 2);

2. (my favourite) mid = (high + low) >>> 1;
I'll leave you to work out how it works.

Winston
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Charles Sexton wrote:code that works.....but does not work if mid or high is ever greater than maximum size of int....


Well done.

And just FYI, there are two ways of solving that problem that will work if high and low are always 0 or positive (which is normal for an index):
1. mid = low + ((high - low) / 2);

2. (my favourite) mid = (high + low) >>> 1;
I'll leave you to work out how it works.

Winston



Thank you.....
 
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Charles..
Why is that 4 in the if() condition hardcoded in your program. Does this program designed for particular length of Array?



 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Surinder Mehra wrote:Charles..
Why is that 4 in the if() condition hardcoded in your program. Does this program designed for particular length of Array?





I forgot to take that out....I was testing when I put that in.......
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Charles Sexton wrote:

Surinder Mehra wrote:Charles..
Why is that 4 in the if() condition hardcoded in your program. Does this program designed for particular length of Array?





I forgot to take that out....I was testing when I put that in.......

 
Surinder Mehra
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok... No issues!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!