• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Confused about binary search algorithm

 
Charles Sexton
Ranch Hand
Posts: 247
  • 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......
 
Winston Gutkowski
Bartender
Pie
Posts: 10430
63
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: 247
  • 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: 247
  • 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: 247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
edited:

inefficient code....see code below
 
fred rosenberger
lowercase baba
Bartender
Posts: 12149
31
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: 247
  • 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: 247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
removed
 
Charles Sexton
Ranch Hand
Posts: 247
  • 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: 247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
removed
 
Winston Gutkowski
Bartender
Pie
Posts: 10430
63
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'?
 
Campbell Ritchie
Sheriff
Pie
Posts: 49472
64
  • 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: 247
  • 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: 247
  • 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: 247
  • 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
Pie
Posts: 10430
63
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
Pie
Posts: 10430
63
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: 247
  • 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: 247
  • 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: 247
  • 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: 247
  • 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: 247
  • 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
Pie
Posts: 10430
63
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: 247
  • 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.....
 
Surinder Mehra
Ranch Hand
Posts: 41
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: 247
  • 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: 247
  • 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: 41
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok... No issues!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic