11 ms·

Let me get this straight. OP searched for an entry in a sorted list using dichotomic search. Okay... Any CS undergrad can do that. Is there something that I'm m

by ohbtvz 4y ago

Let me get this straight. OP searched for an entry in a sorted list using dichotomic search. Okay... Any CS undergrad can do that. Is there something that I'm missing?

dang 4y ago
Some important site guidelines, including: "Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
civopsec 4y ago
It is famously difficult to implement binary search correctly.
- karmakaze 4y ago
  How so, integer overflow? Not so famous that I'm aware.
  - mason55 4y ago
    > Not so famous that I'm aware https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
  - kragen 4y ago
    it took about ten years from the time of the first purported publication of a binary search algorithm for a correct algorithm to be published it's an algorithm where it's easy to have off-by-one errors that lead to nontermination or incorrect results for certain inputs integer overflow is also a problem on some platforms, especially java
    - ilyt 4y ago
      I doubt someone spent 10 years trying to implement a binary search. I suspect it is as usual, someone made theoretical invention, then someone else looked at it years later and wrote implementation in evening or two
      - kragen 4y ago
        more likely there were a lot of correct implementations, but they got debugged after the initial publication, and then didn't publish the erratum
forgotusername6 4y ago
Does reading/seeking in a file that large make it harder?
amelius 4y ago
CS solved this problem, but not in such a way yet that we don't have to think about it anymore. If Python's dict implemented all of this under the hood then it could be called a solved problem.
- genericlemon24 4y ago
  https://docs.python.org/3/library/bisect.html https://docs.python.org/3/library/bisect.html

by ohbtvz 4y ago

Let me get this straight. OP searched for an entry in a sorted list using dichotomic search. Okay... Any CS undergrad can do that. Is there something that I'm missing?

dang 4y ago

Some important site guidelines, including: "Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html

civopsec 4y ago

It is famously difficult to implement binary search correctly.

karmakaze 4y ago
How so, integer overflow? Not so famous that I'm aware.
- mason55 4y ago
  > Not so famous that I'm aware https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- kragen 4y ago
  it took about ten years from the time of the first purported publication of a binary search algorithm for a correct algorithm to be published it's an algorithm where it's easy to have off-by-one errors that lead to nontermination or incorrect results for certain inputs integer overflow is also a problem on some platforms, especially java
  - ilyt 4y ago
    I doubt someone spent 10 years trying to implement a binary search. I suspect it is as usual, someone made theoretical invention, then someone else looked at it years later and wrote implementation in evening or two
    - kragen 4y ago
      more likely there were a lot of correct implementations, but they got debugged after the initial publication, and then didn't publish the erratum

forgotusername6 4y ago

Does reading/seeking in a file that large make it harder?

amelius 4y ago

CS solved this problem, but not in such a way yet that we don't have to think about it anymore. If Python's dict implemented all of this under the hood then it could be called a solved problem.

genericlemon24 4y ago
https://docs.python.org/3/library/bisect.html https://docs.python.org/3/library/bisect.html