Given
a sorted array of 0’s and 1’s. Find out the no. of 0’s in it.
Since Array is sorted already, it is better to use Binary search.
public class BinarySearch { static int binarySearch(int a[], int low, int high){ if(low > high) return -1; int mid = (low+high)/2; if((mid !=a.length-1) && a[mid] != a[mid+1]){ return mid+1; } else if (a[mid] == 0){ low = mid+1; return binarySearch(a, low, high); } else{ high = mid-1; return binarySearch(a, low, high); } } public static void main(String args[]){ int a[] = {0,0,0,1,1,1,1}; System.out.println(binarySearch(a, 0, a.length-1)); } }
Output
3
No comments:
Post a Comment