Concept - Verbose
Suppose you've got a list of sorted numbers.
You know it's 1000 digits long, but that's all. It might look something like this.
The Start: [1, 3, 8, 10, 90, 95, 1000, 1035, ..]
The End : [.., 191283, 193048, 193888, 881931, 882100]
Problem: Find the position of a target number in this sorted list. For example, find the position of the number 40,000.
How would you go about doing this in the fastest way?
Approach 1: Brute Force
You could just go through the list one number at a time until you find your number. So how long will this take on average?
The list is 1000 digits long. And your target will sometimes be at the end beginning, and other times toward the end.
On average it'll be in the middle. So on average we'll hit 500 digits before finding our target. Reframing this, it takes us about 1000/2 or 500 iterations.
Assuming n is the length of the list, the runtime is O(n/2). This simplifies to O(n).