Iterative binary search int bsearch(int* al int size, int x) int low=0, high=size-1 while (low<=higt int mid=(low+high)/2 f(a[mid<x low-mid+1 else if (x<a[mid]) high=mid-1 else return mid; return -1 ni+1<=ni/2 ie.ni<=(N1)2i-1} N stops at 1 or below there are at most 1+k iterations where k is the smallest such that(N1)/2Kk-1}<=1 so k is at most 2+log(N-1) O(log N)12 int bsearch(int* a[],int size,int x) { int low=0, high=size-1; while (low<=higt) { int mid=(low+high)/2; if (a[mid]<x) low=mid+1; else if (x<a[mid]) high=mid-1; else return mid; } return -1 } Iterative binary search: n=high-low n_i+1 <= n_i / 2 i.e. n_i <= (N-1)/2^{i-1} N stops at 1 or below there are at most 1+k iterations, where k is the smallest such that (N-1)/2^{k-1} <= 1 so k is at most 2+log(N-1) O(log N)