aspose file tools*
The moose likes Beginning Java and the fly likes Confused about binary search algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Confused about binary search algorithm" Watch "Confused about binary search algorithm" New topic
Author

Confused about binary search algorithm

Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 199
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

Joined: Mar 17, 2011
Posts: 8427
    
  23

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

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
binary search is in insertion sort order(ascending and alphabetically);
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 199
edited:

inefficient code....see code below
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11499
    
  16

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


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
removed
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
removed
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8427
    
  23

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

Joined: Oct 13, 2005
Posts: 40052
    
  28
Charles Sexton wrote:removed
Don't

That makes replies look like nonsense.
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Mar 17, 2011
Posts: 8427
    
  23

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

Joined: Mar 17, 2011
Posts: 8427
    
  23

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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Mar 17, 2011
Posts: 8427
    
  23

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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Aug 06, 2013
Posts: 32
    
    1
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Sep 26, 2013
Posts: 199
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

Joined: Aug 06, 2013
Posts: 32
    
    1
ok... No issues!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Confused about binary search algorithm