Input: SORTED array, target

Output: element_index or -1 if is not present in array

Complexity: $O(\log{i})$, where i — target index

Algorithm:

int *step* = 0; 
*target* == a[0] → printf(0); exit(); 
*target* < a[0] → printf(”No such element in array”); exit(); 
*target* > a[0] → *step* = 1; 
while(1) {
	*target* == a[step] → printf(step); exit(); 
	*target* < a[0] → binarySearch(array[step / 2:step], target); exit(); 
	*target* > a[0] → *step *= 2*; 
	if (step*2 < n) {
		step *= 2; 
	} else {
		// step*2 is out of bounds
		binarySearch(array[step:n-1], target); 
		exit();
	}

}