• 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
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Recursive binary search

 
Greenhorn
Posts: 21
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello. I've attempted to code a recursive version of a binary search algorithm. It seems to be working, but I would love to hear feedback from you guys.



Aside from your general opinion on the code logic in this algorhitm, I am also interested to hear what do you think about the parameter list. The method relies on user giving correct arguments to the parameters. Is this approach ok?
 
Saloon Keeper
Posts: 3415
149
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Dawid,

I see no problem with your 'binarySearchRecursive' method, it could be slightly shorter here and there (for instance your 'else if'' on line 30 is superfluous, since tou already tested for '==' and '<').

My problem is that you let the user of that method input all these arguments. For the user it should be sufficient if he/she just specifies the array and the value to search for. Why should the user have to specify the begin index and the end index?

So, my suggestion is to reduce the parameters of 'binarySearchRecursive' to two: the array and the value to find. I would then have a private helper method 'binarySearchRecursiveHelper' that contains all these parameters. Your original 'binarySearchRecursive' could then simpy be:

Lastly: if the value is not present, your return value is -1. That is okay, but do have a look at the method 'Arrays.binarySearch' and the value that this method returns. What do you think about such a return value?
 
Sheriff
Posts: 13569
223
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree with all of Piet's points. Additionally, you could use names that express intent better. You're not doing anyone a favor by using names like a and z instead of more expressive names like start and end or first and last, for example. Making your code cryptic does not make it better. In fact, cryptic code is the worst kind of code you could write.
 
Marshal
Posts: 6974
471
Mac OS X VI Editor BSD Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

Pay attention to indentation. It is equally important as all other points mentioned by other posters.

Lines: 22, 26, 27, 32, 33 are off.


One more thing actually. Since your class is meant to be an Utility, and you called it like that - create private constructor so nobody would instantiate such class, which in turn would require you to make all methods in such class static, which is what you supposed to do.

Class name MyUtilities is fairly poor as well. If I'd tell you, take the first thing you find in MyBox on the table, what would you expect there to find? No need to answer. Now imagine I'd say, go and take the first thing you find in the FruitBox. How your expectations would change? You were more accurate, right? Even more better would be, go and take first fruit you find in the fruit box. So now no ambiguities left. So name things the real names - so everybody (including you) knows what that is.
 
Liutauras Vilda
Marshal
Posts: 6974
471
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:So name things the real names - so everybody (including you) knows what that is.


Actually this needs to be approached from other way round.

"Name the things real names - so you and especially everybody else could understand". You are expected to know what you are doing, while others who see your code may or may not have an idea what you were doing. So as much as possible help from your side is expected.
 
Saloon Keeper
Posts: 10428
223
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You've already heard good suggestions from my colleagues. I'd like to add that method/class names should not contains hints about their implementation. It doesn't matter whether the search is performed through recursion or by looking in a crystal ball, the important part is that it searches. This restriction does not hold for private methods, as private methods are used solely for implementation.

Validate inputs to non-private methods.

Avoid reassigning values to method parameters, especially if the method is a "pure function" (a static method whose outcome depends only on the arguments).

Perform early returns to avoid the "arrow anti-pattern", where large code blocks are scoped deeply.

Finally, don't use magic values for special results. Use an appropriate type instead. In this particular case, I would use OptionalInt as the return type:
 
Dawid Smith
Greenhorn
Posts: 21
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you guys for your opinions. I've tried to change the program according to your suggestions. To sum it up, the changes are :

1)There are only 2 parameters in binarySearchRecursive
2)There is additional method called binarySearchHelper added. Its purpose is to help implementing recursive version of the algorithm.
3)Changes in naming and indendation
4)There is constructor added to class ArraysSortingMethods. Its purpose is to prevent instantiation of the class

What do you think of the current version? Your feedback is greatly appreciated.

 
Liutauras Vilda
Marshal
Posts: 6974
471
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dawid Smith wrote:


I am pleasantly surprised you wrote the comment for private constructor to clarify your intention to your code reader - very well done on that! However, comment is slightly imprecise. Isn't really clear what you mean by empty, whether no parameters specified, or body empty - in anyway, non of these are the reasons which prevent object from instantiation. What prevents is its privatness. So comment probably better would read as: "intentional private constructor to prevent class's instantiation" or similar along those lines.

So you renamed your class. Alright. To ArraysSortingMethods. >? Why? I see one method inside, which performs search within the array. What does it have to do with sorting? If your plans are to have also function(s) which sort array, then give to class some broader name, which covers both. In fact Stephan already suggested seem to be not a bad name for your needs.

Again. You have variables: arr, ar. First they are some sort of abbreviations (personally to me, abbreviations are most annoying things, but that's not the reason to improve). Secondly, they describe implementation details. You don't need to do that, int[] <-- this is what denotes that it is an array, and in particular '[]'. Why you don't want to call them simply "numbers"? If you decide at some point to change data structure they are in, you wouldn't need to rename variable, but again, that's not the main reason to change it, main reason is the clarity, what this array holds...

Try to avoid placing array type definition after variable name. That is unconventional. Plus if you read it out loud it doesn't make sense, because this parameter defines "an array of strings", not an array of args. One less known thing, if you ever decide to change it to variable arguments (so called varargs), and you would have it defined as 'String args...' - you'd get compilation error, while 'String... args' would work just fine.

! Your indentation is off again. Lines 4, 5, 22, 26, 27, 32, 33 and 36 this time (indentation level differs). Plus your braces placing style is different in TestingClass as well as in ArraysSortingMethods class - consistency is important.
 
Liutauras Vilda
Marshal
Posts: 6974
471
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note: don't get annoyed by the things we point out (I know it can be frustrating), but the sooner you become more disciplined, the more better and less chaos in your code will be.
 
Rancher
Posts: 1173
16
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A few things:

1. As Liutauras mentioned before, indentation!

2. Also on the subject of code formatting.  Always use braces.  For instance, I'd rewrite lines 21 and 22 as...


Yes, it's perfectly valid to  leave the braces out.  If you scoff at my suggestion, continue to omit braces in such cases and ever admit to getting bitten by something like...



... I will just point and laugh.  Ok, maybe that's a bit harsh.  I'll probably have some sympathy for you, but you see my point.

3. You might consider sorting the array at the beginning of binarySearchRecursive() if a==0 and z==arr.length-1.

[EDIT: In retrospect number 3 is goofy.  Sorting an unsorted array has O(N log N) complexity in general, which is horrible compared to the expected O(log N) time complexity of a binary search.  Even just verifying that the array is sorted is O(N) and requires you to look at every array element, also ruining the advantage of a binary search over a linear one.  Forget I suggested it.]

 
Bartender
Posts: 10775
71
Hibernate Eclipse IDE Ubuntu
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dawid Smith wrote:Hello. I've attempted to code a recursive version of a binary search algorithm. It seems to be working, but I would love to hear feedback from you guys.


Oddly enough, your program contains the same mistake as almost all binary chops ever written, so don't worry, you're in good company. :-)

The problem is with the expression 'half = (a + z) / 2'.
It may look right, but it contains a dangerous flaw, which you'll likely never reproduce because all the lists you deal with will be too small.

The reason is that it will not always produce the correct result because of integer overflow.
If the sum of a and z is >= 2^31, the result will be a negative number, which the compiler will happily divide by 2, and screw up your lovely calculation.

Luckily, there is more than 1 solution:
1. half = a + ((z - a) / 2) - hopefully fairly obvious.
2. half = (a + z) >>> 1 - as fast as it gets, and guaranteed to work provided a and z are >= 0, but a bit "mystical", and not directly translatable to other languages.

For more info check out this.

Hope it helps.

Winston
 
Piet Souris
Saloon Keeper
Posts: 3415
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Winston,

long time no see! Lovely to hear from you again. How are you doing?

And a cow from me too! Only you would spot that flaw... keep 'm coming!
 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your code looks pretty good and it works fine.

Couple of minor suggestions from me.  

1. Making the support static method binarySearchHelper private - So that it is clear that it is not for client consumption.

2. Probably refactoring the binarySearchHelper method in the following way to make it more readable.



The changes are

  a. Keep the int half = (start + end)/2; statement inside the if block.
  b. If value not found, adjust the value of start and end variables and make the next call.

 
Dawid Smith
Greenhorn
Posts: 21
1
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you guys for all the feedback. I love the discussion that is going on here. I've read every comment and now I got a lot to chew on. Given that there were quite a few important points raised, I will try to address all of them gradually.

Piet Souris wrote:hi Dawid,

I see no problem with your 'binarySearchRecursive' method, it could be slightly shorter here and there (for instance your 'else if'' on line 30 is superfluous, since tou already tested for '==' and '<').

My problem is that you let the user of that method input all these arguments. For the user it should be sufficient if he/she just specifies the array and the value to search for. Why should the user have to specify the begin index and the end index?

So, my suggestion is to reduce the parameters of 'binarySearchRecursive' to two: the array and the value to find. I would then have a private helper method 'binarySearchRecursiveHelper' that contains all these parameters. Your original 'binarySearchRecursive' could then simpy be:

Lastly: if the value is not present, your return value is -1. That is okay, but do have a look at the method 'Arrays.binarySearch' and the value that this method returns. What do you think about such a return value?



else if is superfluous indeed, I don't really know why I did that. As far as the methods parameters go, it seemed like the easiest way to solve the problem. It also seemed like a bad code, but I can't really tell what's good/bad at my level. I tried to improve the method according to your suggestions and I posted it in the topic. What do you think about the second version of the method? Also, I looked up 'binary search' in google and some of the implementations you can find at websites that teach how to code are very similiar to mine - they rely on the user to specify begin/end index. Why is that the case when there are better solutions? Lastly, where can I find the implementation of 'Arrays.binarySearch' method you have mentioned?
 
Winston Gutkowski
Bartender
Posts: 10775
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dawid Smith wrote:Thank you guys for all the feedback.


You're welcome.

One other thing to think about (although I may get some disagreement here):
Arrays.binarySearch() does one other very useful thing, at almost no cost to the search itself.

If the search fails, it returns the index where the missing value would be inserted as a negative value. Some purists regard this as unnecessary, but to me it's simply adding value by providing a by-product of a calculation that you're already doing.

Such things have to be thought through carefully, but in this case I think utility trumps the bit of extra documentation needed.

HIH

Winston
 
Marshal
Posts: 65108
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:. . . utility trumps the bit of extra documentation needed. . . .

. . . and in this case it maintains the old convention that a negative value returned represents, “not found”.
 
Stephan van Hulst
Saloon Keeper
Posts: 10428
223
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:If the search fails, it returns the index where the missing value would be inserted as a negative value. Some purists regard this as unnecessary, but to me it's simply adding value by providing a by-product of a calculation that you're already doing.


I agree it's very useful. What gave me a headache is the terrible way they return the value. -2 means "The value was not found, but if we had found it, it would be at index 1".

Instead, the method should have returned an object containing the index and a boolean value indicating whether the search was successful.
 
Piet Souris
Saloon Keeper
Posts: 3415
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No Object, please! I always have to use pen and paper to recalculate the index, and I like to keep it that way.
 
Dawid Smith
Greenhorn
Posts: 21
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ryan McGuire wrote:
Yes, it's perfectly valid to  leave the braces out.  If you scoff at my suggestion, continue to omit braces in such cases and ever admit to getting bitten by something like...



... I will just point and laugh.  Ok, maybe that's a bit harsh.  I'll probably have some sympathy for you, but you see my point.



You have a point. Very recently I wasted like 30mins trying to find a logical error in my code. The mistake was similiar to your code example
 
Dawid Smith
Greenhorn
Posts: 21
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

Dawid Smith wrote:


I am pleasantly surprised you wrote the comment for private constructor to clarify your intention to your code reader - very well done on that! However, comment is slightly imprecise. Isn't really clear what you mean by empty, whether no parameters specified, or body empty - in anyway, non of these are the reasons which prevent object from instantiation. What prevents is its privatness. So comment probably better would read as: "intentional private constructor to prevent class's instantiation" or similar along those lines.

So you renamed your class. Alright. To ArraysSortingMethods. >? Why? I see one method inside, which performs search within the array. What does it have to do with sorting? If your plans are to have also function(s) which sort array, then give to class some broader name, which covers both. In fact Stephan already suggested seem to be not a bad name for your needs.

Again. You have variables: arr, ar. First they are some sort of abbreviations (personally to me, abbreviations are most annoying things, but that's not the reason to improve). Secondly, they describe implementation details. You don't need to do that, int[] <-- this is what denotes that it is an array, and in particular '[]'. Why you don't want to call them simply "numbers"? If you decide at some point to change data structure they are in, you wouldn't need to rename variable, but again, that's not the main reason to change it, main reason is the clarity, what this array holds...

Try to avoid placing array type definition after variable name. That is unconventional. Plus if you read it out loud it doesn't make sense, because this parameter defines "an array of strings", not an array of args. One less known thing, if you ever decide to change it to variable arguments (so called varargs), and you would have it defined as 'String args...' - you'd get compilation error, while 'String... args' would work just fine.

! Your indentation is off again. Lines 4, 5, 22, 26, 27, 32, 33 and 36 this time (indentation level differs). Plus your braces placing style is different in TestingClass as well as in ArraysSortingMethods class - consistency is important.



It seems that everyone here is on the same page regarding my way of naming things. Point taken. I need to put effort into making it as clear as possible. Also, incosistent way of using brackets and incorrect indentation.
I've got a question regarding private constructor in my class. I understand that ArraysSortingMethods(bad name, I know) is like utility type of class so it should be static and it shouldn't be instantiated so we create private constructor to prevent it. It may be a silly question but..why do we that? Shouldn't it be obvious for the user of the class that instantiation doesn't make sense?

Liutauras Vilda wrote:Note: don't get annoyed by the things we point out (I know it can be frustrating), but the sooner you become more disciplined, the more better and less chaos in your code will be.



No worries. I am grateful for feedback I get from all of you

Note : I am addressing specific comments now but obviously everyone is more than welcomed to chime in
 
Stephan van Hulst
Saloon Keeper
Posts: 10428
223
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dawid Smith wrote:Shouldn't it be obvious for the user of the class that instantiation doesn't make sense?


You'd be surprised how many people try to do this:
 
Piet Souris
Saloon Keeper
Posts: 3415
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My convention is (for years now): if an if-expression only has one expression following, I put that expression on the same line, right behind the if. I do not like to spill two lines with braces for this situation, looking ugly.
So

instead of

I do the same for for-loops.
 
Sheriff
Posts: 6127
157
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's a bit non-standard.  From a maintenance view, it's easier to add a statement to the second form that the first.
 
Rancher
Posts: 3305
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
True that consistent braces are a little easier to add lines to.  However, I find that more concise styles like this make it easier to see the meat of the functionality in one screen or less, without so much scrolling around.  Perhaps it's an acquired taste, but it's one  I share with Piet I think.
 
Dawid Smith
Greenhorn
Posts: 21
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:You've already heard good suggestions from my colleagues. I'd like to add that method/class names should not contains hints about their implementation. It doesn't matter whether the search is performed through recursion or by looking in a crystal ball, the important part is that it searches. This restriction does not hold for private methods, as private methods are used solely for implementation.

Validate inputs to non-private methods.

Avoid reassigning values to method parameters, especially if the method is a "pure function" (a static method whose outcome depends only on the arguments).

Perform early returns to avoid the "arrow anti-pattern", where large code blocks are scoped deeply.

Finally, don't use magic values for special results. Use an appropriate type instead. In this particular case, I would use OptionalInt as the return type:



I must admit  that this is code is quite overwhelming for me now. I need to get familiar with throwing exceptions,var type,OptionalInt class and arrow anti-pattern to try to grasp it. As of now though, I would like to address 2 things. Firstly, there are lots of detailed comments in your code. Is this how professionally written code should look like or you did it to help beginner programmers understand what is going on there?
Secondly, by saying "don't use magical values for special results" I assume you refer to my code returning -1 if the desired value is not found. Is my approach inherently bad there? Anyways, thank you very much for such a detailed answer. I need to study it more.
 
Dawid Smith
Greenhorn
Posts: 21
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Dawid Smith wrote:Hello. I've attempted to code a recursive version of a binary search algorithm. It seems to be working, but I would love to hear feedback from you guys.


Oddly enough, your program contains the same mistake as almost all binary chops ever written, so don't worry, you're in good company. :-)

The problem is with the expression 'half = (a + z) / 2'.
It may look right, but it contains a dangerous flaw, which you'll likely never reproduce because all the lists you deal with will be too small.

The reason is that it will not always produce the correct result because of integer overflow.
If the sum of a and z is >= 2^31, the result will be a negative number, which the compiler will happily divide by 2, and screw up your lovely calculation.

Luckily, there is more than 1 solution:
1. half = a + ((z - a) / 2) - hopefully fairly obvious.
2. half = (a + z) >>> 1 - as fast as it gets, and guaranteed to work provided a and z are >= 0, but a bit "mystical", and not directly translatable to other languages.

For more info check out this.
Winston



Thank you for your input. I've read the blog you linked and I found it very interesting. Since the int range is quite large, I wouldn't even think that it may not be enough. Solution #1 you presented make sense. What about just using long instead of int though? Wouldn't that solve the problem as well?

Regarding implementation of binary search, I've found surprising story that comes from Programming Pearls by Jon Louis Bentley. To cut it short, back in the day, Bentley did an experiment which challenged professional programers at Bell Labs and IBM to implement bug-free binary search. The result was that only 10% of the participants succeded. You can read more about it here : https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/    
I am very curious as to what was meant by bug-free implementation. If most participants of the experiment made the same mistake as I did(potential for Integer overflow)then it isn't that interesting since as far as I understand, to reproduce this bug you need very large databases and they hadn't had them in the past. Therefore, it makes sense that they wouldn't have considered a problem like that. However, if so many participants failed the task because of some other logical mistakes, then it would be very surprising to me.



 
Stephan van Hulst
Saloon Keeper
Posts: 10428
223
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dawid Smith wrote:Is this how professionally written code should look like or you did it to help beginner programmers understand what is going on there?


This is how I write professional documentation. Sometimes I'm in the mood and I will add some to example code on these boards.

Is my approach inherently bad there?


Not inherently. There are situations where you might want to do it the way you did. An example is when you're writing code for an embedded device that has limited processing power and memory, because creating extra objects might have a significant impact.

However, you must never write such optimized code without profiling the application first and identifying that indeed, the code you've written is a source of significant latency or memory use.

In general, if a range of values of a data type mean one thing, and another range of values of the data type mean a very different thing, then the data type is probably not appropriate as a return type and you will want to create a custom type. Also, give the type strong semantics. Piet is going to give me a hard time for saying this, but types like Pair are degenerate: When you look at an instance of such a type in isolation, there's no way of telling what the values mean. For this particular exercise, I would write a class like this:

This allows you to write code that is easy to read and understand even if there is no documentation:
 
Piet Souris
Saloon Keeper
Posts: 3415
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan wrote:Piet is going to give me a hard time for saying this


No, I won't! I've said it before: never the twain shall meet..    
 
Winston Gutkowski
Bartender
Posts: 10775
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:What gave me a headache is the terrible way they return the value...


What choice did they have? The value has to be negative, and it has to allow for the fact that "new" object/value might be first.

Oh, and it's an int, since the method predates all the weird and wonderful stuff you can produce today.

And if you can't handle a simple numeric conversion, you're in the wrong business. :-)

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 10428
223
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, they could have returned an object like I demonstrated with SortedSequenceSearchResult, and they could have done it all the way back in Java 1.2.

It's not about whether I CAN produce code that uses the offset negative int correctly. It's about how it makes MY code look. Let's reprise the ListBasedSortedSet.add() method I wrote earlier:

Not terrible, but definitely much less fluent than the first version.
 
Winston Gutkowski
Bartender
Posts: 10775
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Well, they could have returned an object like I demonstrated with SortedSequenceSearchResult, and they could have done it all the way back in Java 1.2.


I'm not arguing that; although the name suggests to me that your class is part of a broader set of "search results" which don't necessarily have to be "sorted".

It also seems perfectly reasonable to me, since an int is a natural choice for a search result, to rationalise its result set into "where I found the element" and "where I would have inserted it".

If you really feel you need to wrap that in a class, I have no particular problem, though I think yours is slightly OTT. Surely:
is sufficient.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 10428
223
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:the name suggests to me that your class is part of a broader set of "search results" which don't necessarily have to be "sorted".


It's the result of a search in a sorted sequence. An unsorted sequence wouldn't have an insertion point for an element that wasn't found.

It also seems perfectly reasonable to me, since an int is a natural choice for a search result, to rationalise its result set into "where I found the element" and "where I would have inserted it".


And that's where we disagree. int is not a natural choice for a search result. Integer (yuck) or OptionalInt (better) might be when the search doesn't have to return an insertion point. When it does, a value of -4 to indicate an insertion point at index 3 is everything but natural.

Surely: [...] is sufficient.


I find it confusing that your foundAt() method returns an index when the element wasn't found, and that the insertAt() method does not return an index when the element was found, even though it's perfectly fine to insert an element with the same value before the found element.
 
Winston Gutkowski
Bartender
Posts: 10775
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:

Winston Gutkowski wrote:the name suggests to me that your class is part of a broader set of "search results" which don't necessarily have to be "sorted".

It's the result of a search in a sorted sequence. An unsorted sequence wouldn't have an insertion point for an element that wasn't found.


Sure it would (or could). First, last or anywhere. That would depend on the nature of the dataset.

And that's where we disagree. int is not a natural choice for a search result. Integer (yuck) or OptionalInt (better) might be when the search doesn't have to return an insertion point. When it does, a value of -4 to indicate an insertion point at index 3 is everything but natural.


I suspect, Stephan, that you are one of the very few people who doesn't see an int as the natural result of a search.
In fact, I think it's so natural that it's perverse not to use one.

Granted, you've explained your reasons for not doing so reasonably well to me, who has been bumping around computers and languages for a few decades now; but you haven't convinced me that you're right.

And my reasoning is as follows:
I'm searching for something, and there are two possible outcomes: I find it, or I don't.
There may be cases when that's all the information I need, but often it won't be, and at the very least an int (as opposed to a boolean) can tell me WHERE an item was found.
So, assuming (a) the dataset is indexable with an int, and (b) knowing where the item was found saves my algorithm time, then I want that information.
However, the smart chaps at Sun also worked out that the "not found" multiverse of int can be used to return the index of the element that our value would be at if it existed. It's hardly their fault that it doesn't fit in absolutely seamlessly with 0-based indexing.

I find it confusing that your foundAt() method returns an index when the element wasn't found, and that the insertAt() method does not return an index when the element was found, even though it's perfectly fine to insert an element with the same value before the found element.


Actually it does. It's just that in both cases it's invalid.

Like I say, I have no great problem with a wrapper class if you think it makes things easier to understand, but AFAIC the result of a search on a sequential dataset, sorted or otherwise, is absolutely an int ... or something very like it.

Winston
 
Winston Gutkowski
Bartender
Posts: 10775
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:...but AFAIC the result of a search on a sequential dataset...


Oops, I meant "random-access"...

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!