Objective: 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:
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:
Output:
(Binary Search)First Index from where 0 starts: 21
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;