So I was in a lecture for @LambdaSchool last night and I wanted to share some of what I've learned about Python, computer science, and runtimes.

WARNING: BIG NERD ENERGY INCOMING

I'm gonna talk here about some sorting algorithms. Specifically linear and binary searches.

We all search for stuff every day. You could search for stuff if it was thrown into a big pile.

Stuff in a big pile is easy to store because you don't have to worry about putting it into a specific place when you're doing it. You just throw it into memory and you're done.

It gets more complicated when you're looking for a thing in that pile of stuff. If you've ever had a messy room/house/office and you're looking for something specific, it's kinda a pain to search through because you don't already have an idea of where it could be.

We're gonna look for the number 12. We're creating a list of numbers that's 100,000 items long.

We're also gonna be choosing numbers between 0 and 10,000,000 to populate that list. Lots of numbers.

The first search (linear search) is pretty simple.

It'll start from the first number in the list and ask itself: "Is this what I'm looking for?"

If so, great. If not, it'll move on to the next number and repeat.

That O(n) thing is a way that we describe the efficiency of this method.

All this means is that in the worst case scenario, we might have to go all the way through every single number in this list and perform this operation on every single thing.

That's great if your list is small. You can zip right through those elements in no time flat.

However, if you're working through a database with millions (or even billions) of entries, it might get kinda tedious. Then imagine having to do that over and over and over again...

That's where a binary search comes in handy.

A binary search will reduce the size of what you have to search for by about half every time it runs. It makes the operation much smaller and more efficient with each cycle.

We call that O(log n). Basically it means that the number of operations we have to do will increase as we have more inputs (more numbers we have to search through), but it does so at a very reduced rate.

Binary search has its own caveats. In order to do a binary search, you need your list to be sorted already. Sorting takes time, so there's always that to consider.

However, that being said, the time it takes to sort your list is usually a good investment down the road.

So what does that mean in terms of runtime?

We're gonna run both searches and then compare the runtimes.

These are still crazy small numbers, but you have to think about it in terms of proportion.

The binary runtime is WAY faster than the linear runtime because it technically has less to do. It doesn't have to work as hard in order to return its result.

It's kinda like if you were searching for a person in a phone book.

If you're looking for a last name starting with W, you don't need to search in the first half of the phone book.

So you throw that half out and search again, but you keep on shrinking what you need to check.

The point here is this:

Python is pretty cool. I never knew that something we take for granted like searching for data could have so many different approaches.

#webdev #computerscience #data

EDIT: I should have said search instead of sorting algorithms. I'm so lame.

Twitter, edit button plz. Thanks!

By the way, binary search efficiency becomes WAY more evident the more zeroes you add to the end of one of these things for your range and the number of elements you're searching through.

The binary search blows linear search out of the water in terms of time/effort expended.