**Objective**: 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 + (end–start)/2; | |

if(arrA[mid]==0 && arrA[mid–1]==1) | |

return mid; | |

else if(arrA[mid]==0 && arrA[mid–1]==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.length–1)); | |

} | |

} |

**Output**:

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

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;