Forums Register Login

Binary Search Algorithm

+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

William Koch wrote:I prefer to use recursion



Why in the world do you want recursion for this application? Its a bad fit.
+Pie Number of slices to send: Send
So I assume you recommend just using loops?
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

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.
Where does a nanny get ground to air missles? Protect this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 1034 times.
Similar Threads
Algorithm-Please help guys!!!
Help me review for final (Java with Data Structures)
How would you design this java class
Binary Tree and Array
Algorithm Help
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 16:13:05.