Win a copy of Learning Java by Building Android Games this week in the Android forum!

- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Bear Bibeault
- Jeanne Boyarsky
- Tim Cooke

Sheriffs:

- Knute Snortum
- Junilu Lacar
- Devaka Cooray

Saloon Keepers:

- Ganesh Patekar
- Tim Moores
- Carey Brown
- Stephan van Hulst
- salvin francis

Bartenders:

- Ron McLeod
- Frits Walraven
- Pete Letkeman

posted 1 year ago

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!

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!

posted 1 year ago

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.

posted 1 year ago

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.

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.

posted 1 year ago

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.

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

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

where

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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 wrote:EDIT: Actually, a call to a correct implementation of

binSearch()would probably look more like this

wherebinSearch()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.

posted 1 year ago

Why can't you call a binSearch() method that you implemented yourself? I don't see any reason why you can't do that.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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 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.

posted 1 year ago

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.

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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?

@OP: can you show us that assingment?

posted 1 year ago

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 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.

posted 1 year ago

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.

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Piet Souris

Master Rancher

Posts: 2905

98

posted 1 year ago

@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... )

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... )

posted 1 year ago

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.

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!