# Find the Index from which 0 starts

Objec­tive:  Given an array of inte­ger which 1’s fol­lowed by 0’s. Find the start­ing index of 0.

Exam­ple:

```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
```

Sim­i­lar Prob­lem: Find the increas­ing OR decreas­ing point in an array

Approach 1: Lin­ear Search:

Nav­i­gate the array and look for first occur­rence of 0.

• Han­dle the edge cases.
• Time Com­plex­ity: O(n)

Code:

Approach 2: Binary Search

• Mod­ify the binary search.
• If mid ele­ment is 0 and left neigh­bor is 1, return the mid index
• If mid ele­ment is 0 and left neigh­bor is 0, Do a recur­sive call on the left half of the array (start, mid).
• If mid ele­ment is 1, Do a recur­sive call on the right half of the array (mid+1, end).
• Han­dle the base cases (see the code).

Time Com­plex­ity: O(logn)

Code:

Out­put:

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

#### You may also like...

• lipsa patel

Line 4 and 5 are not required
If (start > end) return 0;

For­got to han­dle the base case where there are only 2 ele­ments
//If there are only two ele­ments
if (end == start + 1) {
if (array[start] == 0) {
return start;
} else if (array[end] == 0) {
return end;
} else {
return –1;
}
}

Also for­got to han­dle the empty array

if (array == null || array.length == 0)
return –1;