Problem Link - Number of 1s in Binary Search
Problem Statement:
You are given a sorted binary array containing 0’s and 1’s. Your task is to efficiently determine the total number of 1’s in the array.
Note: Your implementation should have a time complexity of O(log n), where ‘n’ is the length of the binary array.
Approach:
To solve this problem efficiently in O(log n)
time complexity, we can use binary search to find the first occurrence of 1
in the sorted binary array. Once we find the index of the first 1
, we can easily compute the total number of 1
s by subtracting the index from the array length.
Steps
- Set two pointers:
low
andhigh
to the start and end of the array. - Use binary search to find the first occurrence of
1
:- If the middle element is
0
, move thelow
pointer tomid + 1
. - If the middle element is
1
, move thehigh
pointer tomid - 1
and store the current index as the potential first1
.
- If the middle element is
- Once the first
1
is found, compute the total number of1
s asn - index of first 1
. - If the array contains no
1
s, return0
.
Complexity:
- Time Complexity:
O(log n)
Binary search uses O(log n) time complexity to search for any element in the array of size n. - Space Complexity:
O(1)
No extra Space is used .