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:

public class FirstIndexOfZeroBruteForce {
public static void find(int [] a){
for (int i = 0; i <a.length ; i++) {
if(a[i]==0){
System.out.println("First Index from where 0 starts: " + i);
return;
}
}
//if you have reached here , means 0 is not present
System.out.println("Array does not have a 0");
}
public static void main(String[] args) {
int [] a = {1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0};
find(a);
}
}


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:

public class FirstIndexOfZeroBinarySearch {
public static int find(int [] arrA, int start, int end){
//base case 1:
if(start>end)
return 0;
//base case2: if only one element
if(start==end){
//if that element is 0, then return that index
if(arrA[start]==0)
return start;
if(arrA[start]==1)
return 1;
}
int mid = start + (endstart)/2;
if(arrA[mid]==0 && arrA[mid1]==1)
return mid;
else if(arrA[mid]==0 && arrA[mid1]==0){
return find(arrA,start,mid);
}else //if(arrA[mid]==1){
return find(arrA,mid+1,end);
}
public static void main(String[] args) {
int [] arrA = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
System.out.println("(Binary Search)First Index from where 0 starts: " + find(arrA,0,arrA.length1));
}
}


Output:

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

1 thought on “Find the Index from which 0 starts”

  1. 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;

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.