# 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

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`

### 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;