Find the Index from which 0 starts

Objec­tive:  Given an array of integer which 1’s followed by 0’s. Find the starting index of 0.


int [] a = {1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0};
First Index from where 0 starts: 10

int [] a = {1,1,1};  //No 0 is present
output: Array does not have 0

int [] a = {0,0,0};  //Only 0’s. return the first index
output: 0

Similar Problem: Find the increasing OR decreasing point in an array

Approach 1: Linear Search:

Navigate the array and look for first occurrence of 0.

  • Handle the edge cases.
  • Time Complexity: O(n)


Approach 2: Binary Search

  • Modify the binary search.
  • If mid element is 0 and left neighbor is 1, return the mid index
  • If mid element is 0 and left neighbor is 0, Do a recursive call on the left half of the array (start, mid).
  • If mid element is 1, Do a recursive call on the right half of the array (mid+1, end).
  • Handle the base cases (see the code).

Time Complexity: O(logn)



(Binary Search)First Index from where 0 starts: 21

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

  • lipsa patel

    Line 4 and 5 are not required
    If (start > end) return 0;

    Forgot to handle the base case where there are only 2 elements
    //If there are only two elements
    if (end == start + 1) {
    if (array[start] == 0) {
    return start;
    } else if (array[end] == 0) {
    return end;
    } else {
    return -1;

    Also forgot to handle the empty array

    if (array == null || array.length == 0)
    return -1;

%d bloggers like this: