Algorithms for Work: Array - Rules and Ideas

tl;dr

• Why do we need to sort? To give rules to array ~> to take advantage of rules to reduce the search range.
• The index can be more than just an index.
• The quiz is in the end, try to solve it

Why do we need to sort? Let see.

Array stores many pieces of data with the same datatype and gives you access to them. For example: 7, 2, 6, 4, 11, 23, 5, 1, 5.

It's fine, but every data structure comes with CRUD. You want to search for a value and check whether it exists or not, if yes, how many time.

To find the number 5, you need to go through all the array till you meet it and have no way to make sure you can stop.

To solve this problem, we want to somehow reduce the searching range. We don't want to go through all the array. That's why we want to give the array a set of rules.

We sort it to: 1, 2, 4, 5, 5, 6, 7, 11, 23

Now we can check 1, 2, 4, 5, 5, 6 and stop here, don't need to go further. Why?

Cuz we know that we never find 5 from this point on, every have from this point is greater than 5. That's the set of rules we made and then used.

Same with if you find 3, we just check 1, 2, 4 and stop with the same idea.

You can have any kind of rule you want, but let's use sort for now.

But this is still slow somehow...

They want to make it faster. Why is that? Because if the worst case, we still have to go through all the array if the value we need to find is in the end of the list.

So we have binary search.

The idea is to pick a number in the middle of the current list.

Compare this value to the value we are looking for AND we know where the result will be in (by focusing on the side that can find result and ignore the side that the result can't be in)

We know that it's O(logn) and O(n) time complexity when compare those 2 solutions. And please also see this solution from the POV: "We reduce the search range after every check by half."

This idea can apply to any problem you face in the future,

"Find the rules for it and try to use them to reduce the search range."

To test your solution let come with a quiz

You have 16 gold coins. And one of the coins is fake and has less weight than the real one. Let use this balance scale to find out the fake one.

How many times do you need to use it to 100% confirm that you find the fake coin on every try?

For me, it can be 15 times. I pick 1 coin and put it on the left side, and then try 15 remaining coins on the right side, the worst case, I pick the fake coin last and take it 15 times.

The solution will come in next article, and we will talk about index on that part 2