Number of Guesses in Binary Search?

How do we know the EXACT number of maximum guesses it takes to find a number in a list of numbers, using binary search? Well for one, we know that in general, the binary search algorithm just halves the range of possible numbers after each guess. So if we start with a list of 8 elements, the first "pass" through the algorithm (aka the first iteration of the while loop) will compare the number we are looking for with the middle element of the array (since there are 8 elements, the middle index is rounded down, which leaves a power of 2 elements left to check, more on this later). So since there's 8 elements and we half the list each time, the max guesses should be 3 right? Because 2^3 = 8?? Wrong! Once we get to ONE element in the array to check (in other words, when max and min are the same number), that requires an iteration through the loop to see whether the last, unchecked element is indeed the same as the key. This "extra" iteration is always added to the max number of guesses, which explains why the runtime is always

But why do we floor the log of n?
Well, we can start by writing out some of the max guesses for some sizes of n.

N = 1, Max Guesses = 1.
N = 2, Max Guesses = 2.
N = 3, Max Guesses = 2.
N = 4, Max Guesses = 3.
N = 5, Max Guesses = 3.
N = 6, Max Guesses = 3.
N = 7, Max Guesses = 3.
N = 8, Max Guesses = 4.

You can see that whenever n becomes a power of 2, the max guesses increments by 1. So that's why we floor the log of n, so that we always take the next lowest perfect power of 2.

Yeah... But.. Why?

The truth is, when n=4, and n=7, they have the same number of guesses, even though n is bigger when it is 7 as opposed to 4. The reason is because we truncate the decimal point of any middle index that isn't perfectly in the middle. For example, when n=7, after the first pass, we divide the possible numbers by 2, so 7/2 = 3.5. But since indexing can only be done by integers, this value, when stored inside an int without explicit double casting, is always going to be just 3 (we cut off, or truncated, the decimal point). Repeating again, 3/2 = 1.5 -> 1. So because we truncate decimal points when we find the "middle" index, finding the log of 7 and finding the log of 4 had the same result. Another way to think about this is the log of anything from 4 to 7 is always going to have the same number of guesses, BECAUSE, they are less than the log of 8, which is the bare minimum to have a whole 'nother guess (log 8 is 3, 3 + 1 = 4 which is one larger than 3).

I hope this cleared up some confusion about binary search guesses, some exams actually make you find the number of passes needed to find a specific number (ahem AP Computer Science A), which should be simple since we know the general formula.

Introduction to PID Algorithms


Often times in robotics, you want to have your robot reach a desired sensor point, whether it is driving to a certain distance, or keeping an arm at a certain height. Let's assume that you want your robot to autonomously drive N meters. To accomplish this, one may run motors for a specific time in order to reach that desired place. However, there is too much variation on things like how much battery the robot has at the time, or the state of the motors, or the surface of contact with the drive, momentum and inertia, and more. Usually, if you have tried this method, you might have noticed that the robot goes over the desired distance (called "overshooting"). So, now let's assume you have attached an encoder to the chassis to measure the amount of degrees that have occurred since the beginning of movement. In the code, the robot moves forward until the encoder reads the goal sensor value. This method is better than not using any sensor, yet still causes overshooting because of the aforementioned physical limitations. The solution? A feedback loop that constantly changes the power of the drive motors.

P, I and D

There are 3 components to a PID controller. P, I and D respectively, stand for Proportional, Integral, and Derivative. In basic calculus, integral is just the area under a curve of some function, and derivative is the slope at a specific point on the graph of a function. The function that we work with in PID is called the error value, that, every iteration loop in the algorithm, updates itself to the new error value. The error value is a function that takes time as an input, and returns the setpoint minus the current sensor value, given by:
With that established, let's dive into the proportional term (P). Proportional term is just taking the error value, and multiplying it by some constant (to weight it properly with the other three terms; this is how PID works fundamentally), so it would look something like this:
where kP is a nonzero floating point number.
Intuitively, as the P term increases, the further the robot has to move to get to the point, and as the P term decreases, the closer it is to the setpoint. You could technically just use a P controller without any I or D, but it would oscillate from overshooting to undershooting the goal sensor value, because we did not add any fine tuning with integrals or derivatives.
Now, lets get into the integral term (I). Integral is the area of the graph of the error function of t versus e(t). Mathematically,

where kI is another non zero constant. Intuitively, the integral term increases as the past errors made sum up to a significant amount.
Finally, lets see the derivative term. Again, it is multiplied by some kD constant, but this time it calculates the current slope of the error graph. The expression is as such:
Intuitively, the derivative term calculates the future possible error values! The slope can predict what the motor needed maybe three seconds into the future.

Putting It All Together:

Now that we have each individual term, we can establish a single function that sums up our very algorithm:
So our actual code will have to calculate the error value, and integral and derivative terms, and constantly set that value to the motor.
Finally, one of the hardest things of PID is tuning the constants so that your robot properly reaches it's setpoint. This may take hours, but there are some well known techniques to help you tune (like the Ziegler-Nichols Method).

ArrayList vs LinkedList

This is a simple performance test of arraylists vs linkedlists in the JCF. Linked lists' elements always have the previous element's position in memory's reference, and the next as well. Insertion yields O(1) time, while accessing yields O(n) time.