• Post Reply Bookmark Topic Watch Topic
  • New Topic

Find 1 in a array  RSS feed

 
prabal nandi
Greenhorn
Posts: 28
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!