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:
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.
Learn more about bidirectional Unicode characters
| public class FirstIndexOfZeroBruteForce { | |
| public static void find(int [] a){ | |
| for (int i = 0; i <a.length ; i++) { | |
| if(a[i]==0){ | |
| System.out.println("First Index from where 0 starts: " + i); | |
| return; | |
| } | |
| } | |
| //if you have reached here , means 0 is not present | |
| System.out.println("Array does not have a 0"); | |
| } | |
| public static void main(String[] args) { | |
| int [] a = {1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0}; | |
| find(a); | |
| } | |
| } |
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.
Learn more about bidirectional 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
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;