Find the Index from which 0 starts

Objec­tive:  Given an array of integers 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 the first occurrence of 0.

• Handle the edge cases.
• Time Complexity: O(n)

Run This Code

Code:

Approach 2: Binary Search

• Modify the binary search.
• If the mid element is 0 and the left neighbor is 1, return the mid index
• If the mid element is 0 and the left neighbor is 0, Do a recursive call on the left half of the array (start, mid).
• If the 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)

Run This Code

Code:

Output:

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