Count 1's in a sorted Binary Array
// count 1's in a sorted Binary array
#include <iostream>
int CountOcur(int arr[], int n)
{
int high = n - 1, low = 0;
while (low <= high)
{
int mid = (high + low) / 2;
if (arr[mid] == 0)
low = mid + 1;
else
{
if (mid == 0 || arr[mid - 1] != arr[mid])
return (n - mid);
else
high = mid - 1;
}
}
return 0;
}
int main()
{
int barr[] = {0, 0, 0, 1, 1, 1, 1};
int size = sizeof(barr) / sizeof(barr[0]);
std::cout << CountOcur(barr, size);
return 0;
}
0 Comments