Today I will look at more binary search questions updating this blog as I go!

I got confused halfway through so watched this video:
How to look for duplicates - space constraint
It gave a great tip. To save on space you can make an element negative (or flip in another way) in an array to show that you have seen that index.

Question:

Find the duplicated Integers

The integers are in the range 1...n

The array has a length of n+1

• First spot is that n = length -1 and is the highest possible value
• When you optimise this one for space you need to look for which half of the possible range has more numbers in it.
• Always when ceiling and floor converge then it is probably time to do something

Question 2 of the day:

Sort scores

const unsortedScores = [37, 89, 41, 65, 91, 53];
const HIGHEST_POSSIBLE_SCORE = 100;

sortScores(unsortedScores, HIGHEST_POSSIBLE_SCORE);
// returns [91, 89, 65, 53, 41, 37]

How can we do this quicker than O(n lg(n))

• First tip was to make an array with all of indexes 0...HighestPossible
• Then we add to a sorted array when there is a value in there

It seems to be all about building a toolkit of algos to solve any problem