Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the Index from which 0 starts

Objec­tive:  Given an array of inte­ger which 1’s fol­lowed by 0’s. Find the start­ing index of 0.

Exam­ple:

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

Sim­i­lar Prob­lem: Find the increas­ing OR decreas­ing point in an array

Approach 1: Lin­ear Search:

Nav­i­gate the array and look for first occur­rence of 0.

  • Han­dle the edge cases.
  • Time Com­plex­ity: O(n)

Code:

Approach 2: Binary Search

  • Mod­ify the binary search.
  • If mid ele­ment is 0 and left neigh­bor is 1, return the mid index
  • If mid ele­ment is 0 and left neigh­bor is 0, Do a recur­sive call on the left half of the array (start, mid).
  • If mid ele­ment is 1, Do a recur­sive call on the right half of the array (mid+1, end).
  • Han­dle the base cases (see the code).

Time Com­plex­ity: O(logn)

Code:

Out­put:

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

You may also like...

  • lipsa patel

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

    For­got to han­dle the base case where there are only 2 ele­ments
    //If there are only two ele­ments
    if (end == start + 1) {
    if (array[start] == 0) {
    return start;
    } else if (array[end] == 0) {
    return end;
    } else {
    return –1;
    }
    }

    Also for­got to han­dle the empty array

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