posted 5 years ago

This question was asked to me in an interview.. (which obviously i couldn't clear)

--> There's an sorted array of integers, only 0's and 1's. arranged such that all 0's are on the left and 1's on the right. We need to write the best possible algo to find the position of the first occurrence of "1" in the array.

E.g: 000000111111

function should return : 6 as answer.

i tried with many algo's but ended up using brute force only. Can someone solve this...

--> There's an sorted array of integers, only 0's and 1's. arranged such that all 0's are on the left and 1's on the right. We need to write the best possible algo to find the position of the first occurrence of "1" in the array.

**Note: we cannot use any of the brute force mechanism.**E.g: 000000111111

function should return : 6 as answer.

i tried with many algo's but ended up using brute force only. Can someone solve this...

Stephan van Hulst

Saloon Keeper

Posts: 7961

143

posted 5 years ago

- 1

Well, you could perform a kind of binary search. Check the middle element, if it's a 1 you then repeat the process on the left half of the array, if it's a 0 you check the right half.

A brute search will have an average complexity of O(n), whereas this binary search has a complexity of O(log n).

A brute search will have an average complexity of O(n), whereas this binary search has a complexity of O(log n).

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*