Example : 00001111
Output : 4
Method 1 : in O(n) we can do it . with sequential search.
Method 2 : Binary search.
Yes binary search is useful, as data is sorted.
Just we need to change its conditions for 0 and 1.
lets have a look at Function firstOccurance.
Output : 4
Method 1 : in O(n) we can do it . with sequential search.
Method 2 : Binary search.
Yes binary search is useful, as data is sorted.
Just we need to change its conditions for 0 and 1.
lets have a look at Function firstOccurance.
firstOccurrance(int[] sortedBins) {
int lower = 0;
int upper = sortedBins.length - 1;
while (lower <= upper) {
int middle = 1 + (upper - lower) / 2;
if (sortedBins[middle] == 0) {
lower = middle + 1;
} else {
upper = middle - 1;
}
if (sortedBins[lower] == 1) {
return lower;
}
}
return -1;
}