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!
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 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.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
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.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
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]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
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.
Naziru Gelajo wrote:The Binary search searches for multiple occurrences of a number per row from a text file.
What should this socalled "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 halfinterval search, finding duplicates is not part of the binary search algorithm itself.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
@OP: can you show us that assingment?
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 socalled "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 halfinterval 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.
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.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
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... )
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.
Willie Smits can speak 40 languages. This tiny ad can speak only one:
Why should you try IntelliJ IDEA ?
https://coderanch.com/wiki/696337/IntelliJIDEA
