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: Run Code

Run Code
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: Run Code

Run Code
Output:

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