Homework 1-5
=
###### tags: `Course - Algorithmics`
## Design
* Induction on $n$, where $n = high - low + 1$ is size of array section.
* Base case, $n = 0$
* High must be less than low (line 4), thus the algorithm returns <font color=#0000FF>**Not found**</font>.
* Which is correct because $i$ can't be in an empty section.
* Induction hypothesis
* Assume that for $1 ≤ SectionSize < k$, the algorithm returns <font color=#0000FF>**i**</font> (which means $i$ is in the section), otherwise it returns <font color=#0000FF>**Not found**</font>.
* Show the algorithm in a section of $k$ elements returns <font color=#0000FF>**i**</font> if it's in the section, otherwise it returns <font color=#0000FF>**Not found**</font>.
* In this section of $k$ elements, the Algorithm executes recursive case
* Compares `A[mid]` to `mid`.
1. *Case 1* `A[mid] < mid`
* Since A is sorted, $i$ must in the section ``[mid+1, high]``.
* Which is searched recursively.
* Thus returns result correctly by induction hypothesis, since $1 ≤ k/2 ≤ k$, and of cause for $k/4, k/8,...$
2. *Case 2* `A[mid] > mid`
Since `A` is sorted, $i$ must in the section ``[low, mid-1]``.
Which are correctly searched recursively
3. *Case 3* `A[mid] == mid`
Algorithm returns <font color=#0000FF>**mid**</font>, which is correct because $i = mid$ and it's in the array section.
## Pseudo Code

procedure find_fixed_point(A : array) do
	set low = 1     // low is left endpoint of search interval
	set high = n    // high is right endpoint of search interval
	while low ≤ high do    // binary search
		set mid = ⌊(high + low) / 2⌋
		if A[mid] > mid do
			set high = mid - 1
		end
		if A[mid] < mid do
			set low = mid + 1
		end
		if A[mid] == mid do
			return mid
			break
		end
	end

	if low > high do
		return "Not found."
	end
end

## Analysis
### Time complexity
* Worst case (not found)
* $\Theta(log_{2}{(n)})$
* Average case
* We need to caculate expectation value.
* $E[n] = \sum_{k=1}^{log_{2}{n}} k\times \frac{2^{k-1}}{n}$
* Note that $k\times 2^{k-1} < log{_2}{n}\times 2^{k-1}$
* Then the formula above is bounded by $\sum_{k=1}^{log_{2}{n}} log_{2}{n}\times \frac{2^{k-1}}{n} = \frac{log_{2}{n}}{n}\sum_{k=1}^{log_{2}{n}}2^{k-1}$
* And $\sum_{k=1}^{log_{2}{n}}2^{k-1} = \frac{1-2^{log_{2}{n}}}{1-2} = 2^{log_{2}{n}}-1 = n-1$
* Multiplying it with $\frac{log_{2}{n}}{n}$ and we can get $log_{2}{(n)}$
* Therefore, it's also $\Theta(log_{2}{(n)})$
### Space complexity
* Any case
* $\Theta(1)$