Negative numbers in sorted array
Negative numbers in sorted array
Given a sorted array of integers, find the number of negative numbers.
Expected Time Complexity: O(log n)
Examples
Array: [-5, -3, -2, 3, 4, 6, 7, 8]
Answer: 3Array: [0, 1, 2, 3, 4, 6, 7, 8]
Answer: 0Intuition
Sorted array => binary search
Find last index of number matching condition
If does not match condition - switch search space to other half
if matches condition - save, and reduce search space in current half
---
Complexity
Time - O(log N)
Space - O(1) - iterative
---
