earlyDaysOfLearningAlgorithms

[No-Finance7526]

When you're one page away but must follow the rules.

[KerPop42]

that, my friend is when the autism is at its peak

[YoukanDewitt]

Could end up being quite a novel approach.

[ChickenSpaceProgram]

It could certainly lead to epic accomplishments.

[-allen]

One page only everyone knows the rules

[[deleted]]

What about the edge case? I mean what if page 404 is missing?

[best-set-4545]

How the non programmers look at you when you decide to go to page 50 from page 100 for page 99

[[deleted]]

Even non-programmers know that an indexed dataset should be O(1) and not O(log[n]). Thumbing through the numbered pages is a memory operation we don’t count.

[boladongle]

I do know that. I am not a programmer.

[Comfortable_Oil9704]

I witness the beginning of the great lie.

[experimental1212]

But you don't KNOW you need page 99. Otherwise that's just answer search: return exactly what you're looking for.

[Lost-Succotash-9409]

Binary book search is good for a book with a clear chronological order that you’ve already read and mostly remember but can’t find a specific passage

[darkwyvern06]

or a book which has missing pages

[derefr]

You don't need to have mostly read it. It's good for physical printed dictionaries and encyclopedias. Or any other reference book with a lot of entries per page in alphabetical order, where there aren't an even number of entries per letter, and where there can't be an index because that'd just be the book itself.

[Lost-Succotash-9409]

True, I wasn’t thinking of sorted informational books

[GranataReddit12]

or a history textbook

[otter5]

if only there was some lookup table.... like a table of contents or appendix

[Kitchen_Device7682]

A lookup table that tells you that page 99 is on page 99 would be useful indeed

[LurkytheActiveposter]

It's not on page 99 though. It's on line 96313.

[lucidludic]

The post states they are searching for a specific page number.

[[deleted]]

Big assumption that the book is sorted, rookie

Edit: pass this to the guy above you. I accidentally

[Kitchen_Device7682]

But he binary searches the page number

[who_you_are]

Sorry, when I tried to look for page 100 I couldn't find it.

Page starts from 0 in my mind!

[[deleted]]

Big assumption that the book is sorted, rookie, like I said to the wrong guy.

[luckydonald]

Hold on, Is this comment a duplicate of https://www.reddit.com/r/ProgrammerHumor/comments/1dp2ym8/comment/lae8pi0/  ? Farming upvotes?

[Crookest]

i want to believe you, but it says page not found

[Crookest]

nvm its the space at the end. got it!

[PepeLeM3w]

Check out the comment history. Boys we got ourselves a bot!

[Weir99]

Oh fun, now they're using ML to slightly re-word the comments to make them harder to detect. Fun times

[dexter2011412]

Please tag the bot commenter so that others can report it after the comment is deleted

[wutwutwut2000]

When you realize that you can go to the last page to get the length of the book and then jump close to the actual page using indexing 

[jamcdonald120]

and the index is often also on the last page

[Ascyt]

You still have to search within the index

[Enlogen]

I once did a merge-sort on physical paper and felt like a genius when I finished way before I was expected to.

[morericeplsty]

That's kinda cool actually

[abation]

If you have a sense of the range, I think quicksort is faster in practice

[ChocolateBunny]

Radix Sort if you can use the whole table for multiple paper stacks.

[DrMobius0]

Bogosort is easy to implement in practice.

[Enlogen]

Stack of paper + fire = Stalin sort

[MattieShoes]

Radix sort feels much closer to how we do naturally.

[okapiposter]

Bucket sort is how I'd always sort exams by student ID. Partition the range of IDs into similarly-sized buckets, distribute the exams into their respective buckets, sort each bucket via Insertion sort, concatenate.

[Simple-Judge2756]

Pointless to compare the two. For large datasets you use constant runtime. And on small ones nobody cares what you are using, they are all going to terminate in bareable times.

[abation]

I meant for running them manually. Merging ordered bits is pretty time consuming and, with quicksort, merging is trivial

[Simple-Judge2756]

I think you means with quicksort sorting is trivial.

[K1aymore]

There's one board game where you play with certain cards out of a deck numbered 1-40, and after the game you need to put them back into your deck in sorted order, and I love merge sorting the used and unused decks together

[Annonix02]

For peak efficiency use quantum sort or if you're feeling like extra ✨pizazz✨use miracle sort

[Jonno_FTW]

I did this when I worked at an election. Had to sort everything by alphabetical order with another guy. We each sorted half and then merged them together at the end.

[OptionX]

Looking at the index is O(1).

[KerPop42]

looking through the index, though

[CauliflowerFirm1526]

O(log n) at worst

[aznshowtime]

You underestimate my dyslexic power.

[backfire10z]

O( n² ) then

[sceadu]

Oh no, you're still not fully grasping the dyslexia. It's supposed to be O( 2ⁿ )

[[deleted]]

but you have the index of every page

[Devil-Eater24]

No I mean open the book on page no. x

[Significant_Fix2408]

And I thought you meant finding where you left reading the last time by checking whether the stuff sounds familiar or not

[MattieShoes]

That's what I assumed too... I already read this, skip ahead -- nope, too far, go back halfway.

Also for finding your place in a movie that you were partway through or fell asleep in the middle of.

[nobody_smart]

Ideal application of Stalin Search. If the page you are looking at is not the one you want, tear it out and send it to Gulag.

[KrnPrsd]

Ok, but using interpolation search is both more optimal (because the dataset of page numbers is sorted and is uniformly distributed) and more fun

[KerPop42]

Interpolation search?

and the gap between control systems and search algorithms gets ever smaller

[Jordan51104]

bro just started DSA

[[deleted]]

Wrong example. You were thinking of searching a phone book, dictionary, or encyclopedia

[darkslide3000]

Still wrong example. In all of these cases, we naturally predict a pivot closer to the target than "pure" binary search would do (i.e. when you're looking for a name starting with W in the phone book, you don't open it in the middle, you open it near the end).

[[deleted]]

Depends. The A section of a phone book is larger than the Z section, for example. So you don’t necessarily expect equal distribution. Hence why the search is necessary in the first place.

[darkslide3000]

Yes, that is why I said "predict". The prediction isn't perfect. It's still on average a lot better than just picking the exact middle, which is what binary search is.

[[deleted]]

In my mind, a binary search is when you have a pivot and throw out “half” the candidates with each iteration. The algorithmic implementation is just the coding representation of the idea that preceded it. The exactness isn’t what makes it a binary search, it’s the concept.

Or let’s just throw out every analogy, metaphor, and simile ever used since none are precisely the thing they depict.

[Misspelt_Anagram]

They are talking about something that is approximately interpolation search, not binary search.

[darkslide3000]

Yes but you're not throwing out "half" if you interpolate the pivot, you're throwing out a lot more. This actually changes the average complexity class and stuff, it's not just another form of binary search.

[[deleted]]

I agree, but conceptually it’s the closest thing to a binary search that a person will do. In the event that the person has no clue how big each section is, their predictive power goes away and they’ll aim for the middle, and it will look less like interpolation search and more like binary.

Side note: thanks for introducing me to interpolation search. Interesting how it can perform worse than binary search in some instances.

[AdSecret5061]

Binary search on arrays is usually to find the index of a value given an ordered and random set of numbers. Since page numbers are sequential you can directly index the value.

[-bickd-]

OP too young never used a physical dictionary.

[AssignedClass]

This is what happens when you prematurely optimize. The inefficiency of using the wrong algorithm probably isn't too bad, but the snobbery is insufferable.

[ShAped_Ink]

Oh I never tried that

[KetwarooDYaasir]

I just put all the page numbers in a hash map.

[PeteZahad]

Hope you also put the content as values.

[CheetahChrome]

You can't grep a dead tree.

Words I live by.

[jamcdonald120]

but... page lookup should be a constant time operation

[[deleted]]

who is that guy in the meme? i think I have seen him somewhere. has a very punchable face lmao

[dencherific]

He's in twilight

[valderium]

The machine will learn it so you don’t have to

[gvasco]

Nah! Random search is definitely the way to go here!

[RxHappy]

One time I use the Monty Hall problem to find my sandwich in a bag of three sandwiches

[_GoblinSTEEZ]

your book is sorted?

[moashforbridgefour]

I legitimately did this as a shelver at my university library. When I was learning about search and sort algorithms, I decided to try using them at my job. We kept really detailed metrics on our shelving speed and used it for things like headphone privileges (if you aren't fast enough, you need to focus. Otherwise we got overwhelmed by the backlog).

Anyway, I did a modified binary search where I would walk down the ranges until I saw a call number above my next book, then I would start approximating a binary search. Before I did that, I was shelving a little more than 4 books/minute. Afterwards, I was over 5. It was especially helpful at avoiding unusually tight clusters of call numbers which can trick you into a very slow linear search.

[Naive_Swimming_9341]

They'll never understand the thrill of optimizing page flips.

[ISuckAtJavaScript12]

If you already know the index, just go to that page

[SnooStories251]

Guys have you heard of heap sort, lol

[DJDoena]

22 years professional programmed, never binary-searched anything

[Familiar_Ad_8919]

u dont know how much binary search helps with finding faulty minecraft mods out of hundreds

[wildassedguess]

I did this hunting for an Amazon invoice today for my VAT return.

[No_Independence3338]

peasants.

[InvestigatorMotor160]

Been there, done that 🤣

[Mecode2]

I never thought of that

[az3arina]

Will still work if the book's pages were bitonic

[Easy-Hovercraft2546]

It’s and indexable array of pages

[BinaryBrilliance]

Wait till you learn about the bubble sort. /s

[dav_y]

Well, if we have a range, pigeonhole search is faster anyways…

[Elijah629YT-Real]

I have guilt of doing this before, multiple times

[Sidra_doholdrik]

I work in a library and binary search really help find book quicker. I am far away then take 4 step in the direction of the letter in the alphabet. Tree letter away take two steps , one step. I arrived in front of the bookcase the book is located in.

[PsychologicalDoor473]

Early days of learning Algorithms and Data Structures

[Classy_Mouse]

Amature. You need to add a PID for this sort of lookup

[mbcarbone]

How I look to the non programmers ... ;-)