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.

Example:

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)

Code:



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)

Code:



Output:

(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.
__________________________________________________

  • 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: