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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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;