1, Binary Search
On sorted array!
public static int binarySearch(int e, int[] array, int low, int high) {
while(low <= high) {
int mid = (low+high)/2;
if(e == array[mid]) return mid;
else if(e < array[mid]) high = mid -1 ;
else low = mid + 1;
}
return -1;
}
On Rotated sorted array:
while(low <= high) {
int mid = (low+high)/2;
if(array[mid] == e) return mid;
if(array[mid] < array[high]) { //the 2nd half is sorted
if(e > array[mid] && e< array[high])
low = mid+1;
else
high = mid-1;
}
if(array[low] < array[mid]) { //the 1st half is sorted
if(e < array[mid] && e> array[low])
high = mid-1;
else
low = mid+1;
}
}
Rotate array by position x:
Reverse the whole array, then Reverse 0~x-1, then Reverse x~size-1.
2, Fibonacci
f(n)= f(n-1)+f(n-2)
对于实现函数calculateFibo(int index)，可以用while loop来逐一计算每个index上的fibo直到到达指定的index；也可以recursive地调用f(n-1) f(n-2)。
对于recursive的方法，类似于一个深度为n的tree，每向下扩展一次结点都会有两个分支，所以O(n)=2*2*2... = 2^n复杂度。