• Post Reply Bookmark Topic Watch Topic
  • New Topic

My method does not seem to be working as intended  RSS feed

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Greetings everyone,

I have a binary search method that searches a 2D array for an integer parameter. Unfortunately however, it does not seem to be finding the correct number of occurences of an item that may appear more than once in the 2D array. Is there something I'm doing wrong? Thanks!

 
Liutauras Vilda
Sheriff
Posts: 4923
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One of the possible problems I see, that after you finish doing your routine within the first row and you jump to a second row, your low and high aren't reset. Look into that first, then see if you have more problems.
 
Paul Clapham
Sheriff
Posts: 22832
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seems to me the algorithm should be "For each row, do a binary search of the columns to find the desired number". But you have another loop over the columns there for no apparent reason.

The relationship between the number returned by that code and the correct number could point towards the errors in your code. For example if it was always off by 1, or always off by a factor equal to the number of columns, that could be a hint. I suggest you look at that relationship.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The code doesn't even look like it does a binary search correctly to me. The inner for-loop index column is never used so what's the point of it? Also, using a for-loop forces you into a constant number of iterations. A binary search is supposed to stop as soon as it finds the number or runs out of elements to search. The number of iterations a binary search takes to do that should be fewer than the number of elements being searched.

The correctness of the code, or incorrectness in this case, is hidden by all the noise of the detailed code jammed into a tight space. That is, the signal to noise ratio is very low.

If you had written that like this instead:

The correctness of the outside loop could be quickly established just by examination. Then it would just be a matter of debugging the algorithm in the binSearch() method to see what was going wrong.

This code assumes that there would be at most only one occurrence of the number in any given row of the nested array. It doesn't account for multiple occurrences in the same row.

EDIT: Actually, a call to a correct implementation of binSearch() would probably look more like this

where binSearch() returns the index of the given number in the specified array or -1 if the number isn't in the array.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That code reminds me of this:
C.A.R. Hoare wrote:There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:EDIT: Actually, a call to a correct implementation of binSearch() would probably look more like this
where binSearch() returns the index of the given number in the specified array or -1 if the number isn't in the array.


Hello Junilu, I'm supposed to implement my own binary Search and not actually call a Binary Search method. The Binary search searches for multiple occurrences of a number per row from a text file.

[Moderator edit: deleted irrelevant parts of long quote]
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why can't you call a binSearch() method that you implemented yourself? I don't see any reason why you can't do that.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And please don't quote an entire response (especially one of mine because they tend to be long) if you can quote just the relevant parts that pertain to your reply. Long quotes make the thread harder to read and follow.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:And please don't quote an entire response (especially one of mine because they tend to be long) if you can quote just the relevant parts that pertain to your reply. Long quotes make the thread harder to read and follow.


Sorry about that Junilu.

To answer your other question, it's for an assignment I can call it later in a driver I create or within the same class itself. Thanks for the advice you, Paul and Liutauras gave me.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:The Binary search searches for multiple occurrences of a number per row from a text file.

What should this so-called "binary search" do if a row had these numbers in it: {4, 4, 4, 6, 9, 10, 15} and you were looking for 4?

Just so you know, the description of your search algorithm does not fit the traditional definition of a binary search and while you may still be employing a half-interval search, finding duplicates is not part of the binary search algorithm itself.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another point: a binary search assumes the collection to search is already sorted. Are you guaranteed to have all the rows in the nested array sorted in ascending order? I say ascending because that's what your code looks like it needs, at least the parts that resemble a correct half-interval search.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And besides: a BinarySearch and counting the total of occurrences do not go well together. The examples given are already enough to see what is wrong with the method. To see that even more simple, follow the method on this simple 1 x 3 array: { { 1, 1, 1} }

@OP: can you show us that assingment?
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Naziru Gelajo wrote:The Binary search searches for multiple occurrences of a number per row from a text file.

What should this so-called "binary search" do if a row had these numbers in it: {4, 4, 4, 6, 9, 10, 15} and you were looking for 4?

Just so you know, the description of your search algorithm does not fit the traditional definition of a binary search and while you may still be employing a half-interval search, finding duplicates is not part of the binary search algorithm itself.


I see what you are saying, that's a good question. It was not specified in the assignment instructions (sent a link of that to Piet). I'm still having problems with my algorithmic implementation and I'm a bit stuck. Not sure why. From my understanding, the way the algorithm should work is that it should go the center value of each column and look for the value. If it is less than the passed integer value, then the high variable is modified to be mid - 1, and if it is higher than the passed integer value, then low is set to be mid + 1 and then a new midpoint is reassigned at the beginning of the code. This cycle continues until there is either no other value (worst case scenario of O(m log n) since this is a 2d Array) or the value is found. Here is what I have done so far. I just can't seem to figure it out. I am upset with myself at this point. I just feel as if I'm REALLY close, but I'm missing a key component.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:

There's no way you can do a binary search on the arrays that you have there because the values in them are not sorted. To do a binary search, each nested array/row MUST be sorted.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Given the example you showed of the kind of data you're dealing with, you're going to have to change your approach. Your data is not sorted and you have repeats. What you want to do absolutely cannot be done with a binary search so I see no point in even trying to force it. The most straightforward way is just to iterate over all the elements of the array. It will be O(n) not O(log(n)), not that it matters much with only that many elements to search. If you had millions of rows, it would be a different story.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Junilu,

I know the assignment. It is guaranteed that the 2D array has the property that each column is sorted, from low to high. And that it is mandatory to use a BinarySearch to get the count of some value. Now, that changes much!

In your style I woud advise OP to create a method 'int[] getColumn(int[][] array, int columnNumber)'. I once wrote a method to transpose a matrix, so that I could work with rows instead of columns, making life just a tad easier.

Having a column, it is quick to test, given the sorted nature, whether the element to be counted can be present in the first place. If not, move on to the next column, otherwise perform a BS and look at the neighborhod of the found index.

To keep 'main' as short as possible, need I mention the terms 'refactoring' and 'code that reads like a kitchen novel'? (guess where I got these terms from...   )
 
Paul Clapham
Sheriff
Posts: 22832
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:I know the assignment. It is guaranteed that the 2D array has the property that each column is sorted, from low to high. And that it is mandatory to use a BinarySearch to get the count of some value. Now, that changes much!


Yes, it's always nice to know the requirements before suggesting how to implement those requirements, isn't it? As far as I can see this is the first time we've been told that.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!