Problem Statement:
THE SOLUTION MUST USE BINARY SEARCH
Given a sorted array and a target value X(the method can only take these 2 thing in!!), determine how many times the value X occurs in the array.
For example, given the array
1,2,2,2,3,3,3,4,5,5,6
and the target value 5, you would return 2 because the array contains two occurrences of the value 5.
Here are my thoughts but I am not sure how to implement them in Java (I also want to do this recursively if possible).
I want to start in the middle of the Array and check if the middle number is the target value.
IF it is not the target value then continue to use binary search until the target value is found.
IF the target values neighbor(s) are not equal to it then we RETURN 1.
Here is the tough part: Once we do find a target value, how do I know how far this target value extends in either direction? I could loop through and find the first occurrence but that would take O(n) (linear time). The point of binary search is to get O(log n) time.
I could use binary search between the point at which I found the target and the end. And use binary search again between the beginning and the point I found the target. Slicing the array essentially. Then when I found the edges of where the target value start and end just subtract the indices and get the answer. I need help implementing this. I am terrible at Java
THE SOLUTION MUST USE BINARY SEARCH
Given a sorted array and a target value X(the method can only take these 2 thing in!!), determine how many times the value X occurs in the array.
For example, given the array
1,2,2,2,3,3,3,4,5,5,6
and the target value 5, you would return 2 because the array contains two occurrences of the value 5.
Here are my thoughts but I am not sure how to implement them in Java (I also want to do this recursively if possible).
I want to start in the middle of the Array and check if the middle number is the target value.
IF it is not the target value then continue to use binary search until the target value is found.
IF the target values neighbor(s) are not equal to it then we RETURN 1.
Here is the tough part: Once we do find a target value, how do I know how far this target value extends in either direction? I could loop through and find the first occurrence but that would take O(n) (linear time). The point of binary search is to get O(log n) time.
I could use binary search between the point at which I found the target and the end. And use binary search again between the beginning and the point I found the target. Slicing the array essentially. Then when I found the edges of where the target value start and end just subtract the indices and get the answer. I need help implementing this. I am terrible at Java