Win a copy of Design for the Mind this week in the Design forum!

# Binary Search Algorithm

William Koch
Ranch Hand
Posts: 76
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

Pat Farrell
Rancher
Posts: 4678
7
Is this a homework assignment, or something real? If it were real, I'd first put the incoming array into a TreeMap. This is overhead, but you can't trust that the input array is properly sorted. The TreeMap would store the value, and how many times it was in the original array.

Then access the TreeMap, which will use a binary or related search and return the value.

If your homework is to implement a binary search, then you should, of course, just do that the hard way.

William Koch
Ranch Hand
Posts: 76
It is a homework assignment. And I did some Google Searching and found solutions to counting occurrences of a Target number in a sorted array the problem is the method can only take in the target number and the array. I prefer to use recursion and I need to use binary search, or like you said "do it the hard way" I am shooting for O(log n) time.

Pat Farrell
Rancher
Posts: 4678
7
By definition, a binary search is O(log N)
Of course, for small samples, the constants that are hidden in Big Oh notation can crush the actual runtime.

It should be a constant times log2 N, since the binary part should halve the number looked at each cycle.

Pat Farrell
Rancher
Posts: 4678
7
William Koch wrote:I prefer to use recursion

Why in the world do you want recursion for this application? Its a bad fit.

William Koch
Ranch Hand
Posts: 76
So I assume you recommend just using loops?

Pat Farrell
Rancher
Posts: 4678
7
A binary search is well defined, you calculate the middle point, check it, decide if you are equal, high or low, then divide the range in half, and pick the middle of that.

You can recurse, but you don't have to.

fred rosenberger
lowercase baba
Bartender
Posts: 12097
30
William Koch wrote:I prefer to use recursion...

That is the wrong way to approach any programming task. You don't start with a tool and say "How can I use this tool to create what I need". An airbrush is a fantastic tool, but I wouldn't use it to build a house.

You start by analyzing what you need to do. You think about it in English (or any other natural language of your choice). You write down the steps, as if you were telling your 10 year old brother/neice/neighbor's child how to do it, and expect them to be able to follow your directions without further input from you.

THEN you start figuring out which tools to use - recursion, singletons, binary searches, etc.

I get that this assignment requires you to use a binary search - sometimes when learning, a teacher dictates such things. But don't put other arbitrary constraints on yourself like "i want to use recursion".

That is just a bad idea.