Problem on time complexity


#1

Given an array A which stores 0 and 1, such that each entry containing
0 appears before all those entries containing 1. In other words, it is like
{0, 0, 0,…, 0, 0, 1, 1,…, 111}. Design an algorithm to find out the small
index i in the array A such that A[i] = 1 using c log n instructions in the
worst case for some positive constant c.


#2

Use the binary search.
Algo:

left=0
right=n-1
while(left<=right)
{
mid=(left+right)/2
if(A[mid] == 1 && (mid == 0 || A[mid-1] ==0)
{
return mid
}
else if(A[mid]==1)
{
right = mid-1;
}
else
{
left=mid+1
}
}