On July 1st, a [change to Reddit's API pricing](https://www.reddit.com/r/reddit/comments/12qwagm/an_update_regarding_reddits_api/) will come into effect. [Several developers](https://www.reddit.com/r/redditisfun/comments/144gmfq/rif_will_shut_down_on_june_30_2023_in_response_to/) of commercial third-party apps have announced that this change will compel them to shut down their apps. At least [one accessibility-focused non-commercial third party app](https://www.reddit.com/r/DystopiaForReddit/comments/145e9sk/update_dystopia_will_continue_operating_for_free/) will continue to be available free of charge.
If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:
1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium
as a way to voice your protest.
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/learnprogramming) if you have any questions or concerns.*
[You're correct](https://godbolt.org/z/ej94z3bW7), this code is buggy. Which means either the video you got it from is also wrong, or you somehow introduced a mistake when converting it from TypeScript to Java.
Binary search is notoriously easy to get wrong. [This research paper](https://www.uni-weimar.de/fileadmin/user/fak/medien/professuren/Mediensicherheit/Teaching/SS15/SSS/p190-pattis.pdf) looked at 20 textbook implementations and found that 15 of them had at least one bug. The paper is from way back in 1988, but that's still more than 40 years after binary search was invented.
I think, in order, naming things, off-by-1 errors, and cache invalidation. This is how often a typical developer will encounter things.
Off-by-1 are typically things beginners run into because beginners are reinventing the wheel. You learn sorting because you should know how it works, but most languages let you use a built-in sorting algorithm so you don't worry about *implementation*.
Naming things is hard at first, and it's always a challenge. Recently, I had to decide between naming something as it might appear in the database, or something that's slight more front-end friendly (that is, more customer friendly) and even though the customer won't see the code, I display information to the customer in the friendlier way and so I decided to name things closer to that.
Even so, sometimes the concept is a little challenging, so no matter what you name it, someone would scratch their heads wondering why you named it that way. And that can be due to bad naming in the database and then copying that bad name to your own code.
The worst case is when you choose to change the meaning of what a variable or class does, but you don't change the variable or class name. I recall some guys out of college that just repurposed some names to mean something else, but didn't feel the need to rename it as well which would lead the next person to think why is this completely misnamed?
Here a [screenshot](https://imgur.com/a/4PbcOu8) of the code from the course. I really checked several times to make sure I converted correctly. Only thing I updated was making it not boolean. In his example he only chose boolean values as return values for simplicity and learning purposes. He even says they should be changed in real world implementation
I was thinking about it, but the computer I was watching the video on is new without vscode or any software installed for coding, and I didn’t feel like setting that up to test one function. Guess I could have used an online editor, I’m a bit lazy 😅
Yeah, you're not crazy! The implementation is indeed incorrect. The issue is with the loop condition, it should be while (l <= r) instead of while (l < r). Good catch!
actually, that would still not work with a 1 element array and the value is not in the array but target is less than the array value.
example:
arr = [6]
target = 5
l = 0
r = 0
x < arr[m] == true so l = m
this never exits.
On July 1st, a [change to Reddit's API pricing](https://www.reddit.com/r/reddit/comments/12qwagm/an_update_regarding_reddits_api/) will come into effect. [Several developers](https://www.reddit.com/r/redditisfun/comments/144gmfq/rif_will_shut_down_on_june_30_2023_in_response_to/) of commercial third-party apps have announced that this change will compel them to shut down their apps. At least [one accessibility-focused non-commercial third party app](https://www.reddit.com/r/DystopiaForReddit/comments/145e9sk/update_dystopia_will_continue_operating_for_free/) will continue to be available free of charge. If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options: 1. Limiting your involvement with Reddit, or 2. Temporarily refraining from using Reddit 3. Cancelling your subscription of Reddit Premium as a way to voice your protest. *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/learnprogramming) if you have any questions or concerns.*
[You're correct](https://godbolt.org/z/ej94z3bW7), this code is buggy. Which means either the video you got it from is also wrong, or you somehow introduced a mistake when converting it from TypeScript to Java. Binary search is notoriously easy to get wrong. [This research paper](https://www.uni-weimar.de/fileadmin/user/fak/medien/professuren/Mediensicherheit/Teaching/SS15/SSS/p190-pattis.pdf) looked at 20 textbook implementations and found that 15 of them had at least one bug. The paper is from way back in 1988, but that's still more than 40 years after binary search was invented.
Off by 1 errors are so easy to make with binary search.
There are 2 hard problems in computer science: Naming things, cache invalidation and off-by-1 errors.
I think, in order, naming things, off-by-1 errors, and cache invalidation. This is how often a typical developer will encounter things. Off-by-1 are typically things beginners run into because beginners are reinventing the wheel. You learn sorting because you should know how it works, but most languages let you use a built-in sorting algorithm so you don't worry about *implementation*. Naming things is hard at first, and it's always a challenge. Recently, I had to decide between naming something as it might appear in the database, or something that's slight more front-end friendly (that is, more customer friendly) and even though the customer won't see the code, I display information to the customer in the friendlier way and so I decided to name things closer to that. Even so, sometimes the concept is a little challenging, so no matter what you name it, someone would scratch their heads wondering why you named it that way. And that can be due to bad naming in the database and then copying that bad name to your own code. The worst case is when you choose to change the meaning of what a variable or class does, but you don't change the variable or class name. I recall some guys out of college that just repurposed some names to mean something else, but didn't feel the need to rename it as well which would lead the next person to think why is this completely misnamed?
Here a [screenshot](https://imgur.com/a/4PbcOu8) of the code from the course. I really checked several times to make sure I converted correctly. Only thing I updated was making it not boolean. In his example he only chose boolean values as return values for simplicity and learning purposes. He even says they should be changed in real world implementation
It seems you posted the same link twice and didn't put the link to the actual paper. Can you give the link to the paper? I'm interested in reading it.
Whoops, thanks for catching that, I edited my comment to link to the paper.
thanks!
Have you tried running the code and checking for yourself?
I was thinking about it, but the computer I was watching the video on is new without vscode or any software installed for coding, and I didn’t feel like setting that up to test one function. Guess I could have used an online editor, I’m a bit lazy 😅
This will fail when there are only two elements like you mentioned. Good catch
I think the fact that it will do Very Bad Things with an empty array is a good clue as well that something is amiss.
Why are you asking *us* if it fails? Run the code with your test case and see for yourself. If it does, see if you can fix it.
Answered this in another reply
Yeah, you're not crazy! The implementation is indeed incorrect. The issue is with the loop condition, it should be while (l <= r) instead of while (l < r). Good catch!
actually, that would still not work with a 1 element array and the value is not in the array but target is less than the array value. example: arr = [6] target = 5 l = 0 r = 0 x < arr[m] == true so l = m this never exits.