Count 1's in a sorted binary array - GeeksQuiz
Given a binary array sorted in non-increasing order, count the number of 1's in it.
{
........while ( lo < hi )
........{
..............int mid = (lo + hi)/2;
..............if ( a[mid]==1 ) { lo = mid + 1; }
..............else.......... { hi = mid - 1; }
........}
.
........if ( a[lo] ==1) return lo+1;
........else..... return lo;
}
// in some cases the checkElementValue(i) may be expensive(like getBadVersion example), so it's better to just check one value in each call.
Read full article from Count 1's in a sorted binary array - GeeksQuiz
Given a binary array sorted in non-increasing order, count the number of 1's in it.
Input: arr[] = {1, 1, 0, 0, 0, 0, 0}
Output: 2
Input: arr[] = {1, 1, 1, 1, 1, 1, 1}
Output: 7
int bsearch(int a[], int lo, int hi){
........while ( lo < hi )
........{
..............int mid = (lo + hi)/2;
..............if ( a[mid]==1 ) { lo = mid + 1; }
..............else.......... { hi = mid - 1; }
........}
.
........if ( a[lo] ==1) return lo+1;
........else..... return lo;
}
// in some cases the checkElementValue(i) may be expensive(like getBadVersion example), so it's better to just check one value in each call.
/* Returns counts of 1's in arr[low..high]. The array is assumed to be sorted in non-increasing order */int countOnes(bool arr[], int low, int high){ if (high >= low) { // get the middle index int mid = low + (high - low)/2; // check if the element at middle index is last 1 if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1)) return mid+1; // If element is not last 1, recur for right side if (arr[mid] == 1) return countOnes(arr, (mid + 1), high); // else recur for left side return countOnes(arr, low, (mid -1)); } return 0;}