• Post Reply Bookmark Topic Watch Topic
  • New Topic

Problem with my binary search?  RSS feed

 
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Righto, so I've crafted a binary search and a sequential search. The sequential search works perfectly fine.

However; my binary search doesn't. If I enter in incorrect data, it tells me the data I entered was incorrect. But if I enter in correct data, my sequential search tells me my datas correct, but binary search tells me I'm still incorrect. Any ideas? Here's my binary search + the test program.



 
Marshal
Posts: 56608
172
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you searching that array as is? You know binary search only works on sorted arrays/lists?

Don't call a method partTwo; it will be very confusing if you come back on it in six months.
 
W Wilson
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Are you searching that array as is? You know binary search only works on sorted arrays/lists?

Don't call a method partTwo; it will be very confusing if you come back on it in six months.


I had forgotten about that at first. I'm currently trying to fix my sort at the moment.

partTwo is fine as this is for an assignment and the name of the method isn't part of the grading. But typically I wouldn't use it as a method name.

Edit: This is my current (and I think final) issue.



The error I get is that int cannot be dereferenced due to compareTo. Any ideas on how I can manipulate this to do what I need it to?

Full code:

 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you using Java7 or Java8? I have seen things similar to that boxed in Java8.

Anyway, if you are using primitives, you can simply apply the > operator to them.
if (myArray[i] > myNumber) ...
 
W Wilson
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Are you using Java7 or Java8? I have seen things similar to that boxed in Java8.

Anyway, if you are using primitives, you can simply apply the > operator to them.
if (myArray[i] > myNumber) ...


I'm using Java8.

The problem with using the operator is that using >, < or = gives me an issue (bad operand types). Apparently the first type is a boolean and the second type is an int. I can't see where the boolean is.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How do you manage to get a boolean to the left of the comparison operators? Please show us the code which produces that error.
And you don't use =. It is ==, probably because a precursor language used the wrong operator for assignment (=) and had to invent == for equality.
 
W Wilson
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:How do you manage to get a boolean to the left of the comparison operators? Please show us the code which produces that error.
And you don't use =. It is ==, probably because a precursor language used the wrong operator for assignment (=) and had to invent == for equality.


This is the full code



The code that the has the error is:



Sure, I could literally do Arrays.sort and have the same result w/o the trouble but I'm trying to practice using a selection sort.

With these operators I get a bad operand error as so:

">, <"



Using "==" gives this error:



I have removed the ">0" from the line with the error while using > or < or == and it would compile, however entering correct data still gives me an invalid return so the sort isn't being sorted properly.
 
Sheriff
Posts: 22846
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


I don't understand what that code is intended to do. Do you want to compare whether the two numbers are equal? Or do you want to know if the first number is greater than the second number? Here's how to do each of those two things:





Or do you want to do something else which I didn't guess at?
 
W Wilson
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:

I don't understand what that code is intended to do. Do you want to compare whether the two numbers are equal? Or do you want to know if the first number is greater than the second number? Here's how to do each of those two things:





Or do you want to do something else which I didn't guess at?


It should be >, because we're comparing the currentIndex to the indexSoFar (the index of the largest item in the array so far). If the current index is larger than the index so far, we update our indexSoFar until there is no index that has a larger value. That index is then returned (because it is used in my selection sort method).

The problem is that
--- Oh christ.

When I made the operator ">" before, it compiled fine yet I still always got the wrong answer for entering the correct data. It just hit me. Selection sort is a method. My test program never called the selectionSort method so my binary search didn't work because though the code was written for the sort, it was never called. Stupid, stupid, stupid.

New issue. My selection sort requires a parameter of (int n). int n refers to the amount of items in the array. I'd like to remove this, in the subtle case that I for instance theoretically don't know how many entries are in my array. Here's what I've tried, that didn't work.



(Much of the commenting is just me saving data in case I have to revert)

Edit: Replaced "int last = n-1" to be "int last = accountNumbers.length-1" and it works.
 
Bartender
Posts: 1840
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the wonderful world of computer programming.
Where you can bang your head against a brick wall for hours on end, and then a colleague walks past, glances at your code, and spots your bonehead error in about two seconds flat.

You were obviously convinced the problem was in your sort method, when the problem was it wasn't being called by your search method.
In hindsight is there anything you think you could have done to spot this problem earlier?

Things that might help:
#1 - Logging. Print all the things. Let the computer tell you what its doing. System.out.println would work, but if you use a logging library you can just switch the messages off in the end (and switch them on again the next time you want to debug).
If you had seen:
Input List: [69, 7, 42]
Sorted List: [69, 7, 42] <---- WTF? Something is wrong here!
7 is not in the list.
Then you may have found your problem earlier.

#2 - Unit tests. Yes I know its an assignment. But writing unit tests around your methods selectionSort and indexOfLargest might have helped.
In this case you could have been certain that your sort method was actually working, and started looking elsewhere for binary search wasn't giving you the expected answer.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
W Wilson wrote:I had forgotten about that at first. I'm currently trying to fix my sort at the moment...

My advice: DON'T.

The two problems are totally unrelated: A sort is a sort, and a binary search is a binary search (that just happens to need sorted data).

So: to sort your array, use:
Arrays.sort(accountNumbers);

Why? Because that sort WILL work, so you can now concentrate on your main problem, which is to get your binary search to work. If you also need to write a sort, deal with that as a separate issue, and plug it in to your search code as soon as you know it works (but NOT before ).

It's called "problem isolation", and it's a big aid in writing good programs: Deal with one thing at a time.

HIH

Winston
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
W Wilson wrote: . . .

The code that the has the error is:

. . .
That should be
if (accountNumbers[currIndex] > accountNumbers[indexSoFar]) ...

Or something like that.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!