Win a copy of Design for the Mind this week in the Design forum!

# Confused about binary search algorithm

Charles Sexton
Ranch Hand
Posts: 241
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
Posts: 10226
58
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: 241
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: 241
binary search is in insertion sort order(ascending and alphabetically);

Charles Sexton
Ranch Hand
Posts: 241
edited:

inefficient code....see code below

fred rosenberger
lowercase baba
Bartender
Posts: 12097
30
So put in a bunch of System.out.println() statements to see what your code is really doing.

Charles Sexton
Ranch Hand
Posts: 241
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: 241
removed

Charles Sexton
Ranch Hand
Posts: 241
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: 241
removed

Winston Gutkowski
Bartender
Posts: 10226
58
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
Posts: 48645
56
Charles Sexton wrote:removed
Don't

That makes replies look like nonsense.

Charles Sexton
Ranch Hand
Posts: 241
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: 241
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: 241
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: 10226
58
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: 10226
58
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: 241
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: 241
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: 241
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: 241
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: 241
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: 10226
58
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: 241
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: 34
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
Posts: 241
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: 241
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: 34
1
ok... No issues!