There are three kinds of actuaries: those who can count, and those who can't.
Liutauras Vilda wrote:So name things the real names - so everybody (including you) knows what that is.
Dawid Smith 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.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
There are three kinds of actuaries: those who can count, and those who can't.
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?
Dawid Smith wrote:Thank you guys for all the feedback.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
. . . and in this case it maintains the old convention that a negative value returned represents, “not found”.Winston Gutkowski wrote:. . . utility trumps the bit of extra documentation needed. . . .
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.
There are three kinds of actuaries: those who can count, and those who can't.
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.
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.
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.
Dawid Smith wrote:Shouldn't it be obvious for the user of the class that instantiation doesn't make sense?
There are three kinds of actuaries: those who can count, and those who can't.
All things are lawful, but not all things are profitable.
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:
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
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?
Is my approach inherently bad there?
Stephan wrote:Piet is going to give me a hard time for saying this
There are three kinds of actuaries: those who can count, and those who can't.
Stephan van Hulst wrote:What gave me a headache is the terrible way they return the value...
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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 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".
Surely: [...] is sufficient.
Stephan van Hulst wrote:
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.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".
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 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.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:...but AFAIC the result of a search on a sequential dataset...
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Liutauras Vilda wrote:Dawid Smith,
CowGratulations, your topic has been published in our CodeRanch Journal August Edition.
A copy of journal you could find here -> https://coderanch.com/wiki/715405/CodeRanch-Journal-August
Other than that, you, as everybody else supposed to get one emailed to you
Yup, yup, yup. Tiny ad:
Smokeless wood heat with a rocket mass heater
https://woodheat.net
|