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.

# Problem on time complexity

**Harsha_1997**#1

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`

}

}