# Topic 2 Exercises
## Exercise 1
* start with *low = A[0]* and *high = A[1]*
* compare *high* with target value *x*
* obviously if *high == x || low == x* then you are already finished
* if not, repeat the following:
* if *x > high*, double the *high* value and make *low* the previous *high* value
* if *x < high*, binary search between *low* and *high*
* if *high == null*, set *high = high + (high - previousHigh)/2* and from then on only increment *high* by *(high - previousHigh)/2n* (instead of doubling) where *n* is the number of times *high* has returned *null*
* the binary search part we know is $O(log(n))$
* the other part of the algorithm is a search which exponentially changes the index, also implying a $O(log(n))$ time complexity

## Exercise 2
* Look at index n/2
* If the value of A[n/2] > n/2, move to index A[n/4]
* If the value of A[n/2] < n/2, move to index A[3n/4]
* Continue this process of either moving up by half the inverval or down by half the interval until either we find the value such that A[i] = i or we find that no such value exists

Since we are using a binary search, the runtime will be $O(log(n))$

## Exercise 3
* First we examine A[n-1]
* if A[n-1] is greater greater than the value we are searching for, we move down by $\sqrt{n}$
* if that value is still greater, we continue to move down by $\sqrt{n}$ until either
* we hit a value greater than A[n-1] at which time we know we have reached $k$ that the value is not in the set
* or we find a value less than the $x$ and we begin to move up until we either
* find the value
* get back to the previous step in which case we know the value is not in the set
* if that value is less than $x$, we go to A[0] and check that value
* if it is greater, than we know $x$ is not in the set
* if it is less than $x$ we move up by $\sqrt{n}$ until we find a value greater than $x$ and we move down by 1 until either
* We find x
* we find x is not in the set

this is essentially a modified binary search, therefore the runtime is $O(log(n))$

## Exercise 4

* First, if n is even check the entry in A[n/2] and A[(n/2)+1] and if n is odd check A[(n-1)/2] and A[((n-1)/2)+1] (i.e. the middle entries).
* If the entries are increasing, check the middle two entries of the bottom half of the array.
* If these entries are increasing, once again check the entries in the bottom half of this half.
* If the entries are decreasing, check the entries in the top half of this half.
* Repeat in this manner until there are just two entries left in the section, the lowest of the two entries is the minimum. **If the lowest is A[0] do one last check to ensure it is smaller than A[n]
* If the entries are decreasing, check the middle entries in the top half of the array
* If these entries are increasing, check the middle entries in the bottom half of this half.
* If the entries are decreasing, check the middle entries in the top half of this half.
* Repeat this until there are just two entries left in the section, the minimum of these entries is the minimum. **If the lowest entry is A[n], check to make sure A[0] is not smaller.

This is also a modified binary search so it will have a $O(log(n))$ runtime.

This algorithm works because the smallest element is always going to be at the end of a decreasing section or at the beginning or end of the sequence. Thus, during every check of the middle two elements, if they are decreasing, then the end of the decreasing section will be to the right in the array. Otherwise, if they are increasing, the decreasing section must be to the left. The only exception would be if the element is at the beggining or end of the array in which case if we end up at the beginning or end, we check the other end.