• Post Reply Bookmark Topic Watch Topic
  • New Topic

recursive search question  RSS feed

 
Steve Shipman
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have this recursive binary search method here:



I need it to return the number of integers equal to my target value instead of my result. I thought of just having a counter, and keeping track of it, if it was found in mid, greater than mid, or less than mid then just count++....But if I did that, the most I could have would be 3. And if there was a 20 element array, there could be 7 of my target in there. So how can I keep track of how many of my target are actually are there? Thanks in advance
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First, could I get you to take a look at our display name policy and then edit your display name to something a little more plausible-sounding? Thanks.

For your question, a quick fix is: one you've found the position of one target, just write two simple loops to scan backward and forward from that position, to find the beginning and end of the target range. A more refined approach would be do both of these as binary searches. I.e. do a binary search between first and result for the start of the target range, and do another binary search between result and last, to find the end. The details for these two searches will be a little different from the method you have now (and from each other). I would recommend writing each search as a separate method, at least initially. All three searches should be somewhat similar though, and after you work out the details of each, you may be able to find ways to refactor your code to reuse common code for all three. Feel free to post more of your attempts here for further feedback. Good luck...
 
Greg Charles
Sheriff
Posts: 3015
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You mean, there could be seven of your target there for example? Of course, in a 20 element array, there could be 20 of your target. The problem is, once you find your target, you just return the index. You can't even get a count of three by your algorithm. However, you can take advantage of the fact that your array is sorted, which is a prerequisite for using a binary search. All the elements matching your target will be between the range of first and last of the recursive call in which you find the target. That will be a smaller range than the original first and last, so you could just search it linearly looking for all occurrences of your target. Or you could search from mid down to first, breaking when you stop matching your target, and then doing the same for mid up to last. Or you could start another binary search with reverse logic, looking for the first element, from first to mid and then from mid to last, that doesn't match your target.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!