Member Avatar for noobjavacoder

First question, is there any difference between binary search and recursive binary search??? I looked through google and everything but couldnt find any useful info. I did find irritative and recursive but that was it.

and second question:

Given a desired search value of 98 and an array with the following sorted integer values:
Index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Value: 1, 12, 28, 35, 49, 62, 73, 86, 98, 120
Indicate the comparisons made in a recursive binary search function, as well as the values for each of the following variables: int low, int mid, and int high.
For example:
1st function call: low = 0 high = 9 mid = 4 val[mid] == 98? no comparisons = 1
2nd function call: low = ? high = ? mid = ? val[mid] == 98? comparisons = 2
3rd function call: low = ? high = ? mid = ? val[mid] == 98? comparisons

i know in binary recursive it takes the 1 and last and then divide by 2 and then, if not found in first half, the search looks in second half. so does it mean for 2nd function it will be low of 4, high of 9 and then mid of 6...?

thanks for all your help guys.

  • 3 Contributors
  • 4 Replies
  • 1K Views
  • 3 Hours Discussion Span
  • Latest Post Latest Post by invisal
Member Avatar for JamesCherrill

A binary search partitions top/bottom halfs, then does the same for the appropriate half and continues until it's found the result. That is a recursive algorithm.
It would be natural to implement that with recursive code. However, it's possible to write the code without using recursion, ie an iterative version, and there may be technical efficiency reasons why you would do so.

so does it mean for 2nd function it will be low of 4, high of 9 and then mid of 6...?

Yes, you've got right idea. But because [4] wasn't the target value there's no point including it in the next search, so [5] - [9] would be better

Edited by JamesCherrill
Member Avatar for invisal

First question, is there any difference between binary search and recursive binary search?

Iterative binary search and recursive binary search are same algorithm with different choice of implementation.

so does it mean for 2nd function it will be low of 4, high of 9 and then mid of 6...?

No, the low would be 5 and high would be 9. Why would you want to include the 4th element in the list while you have already confirm that it is not what you are searching for.

Noted that, iterative binary search usually is faster and more memory efficient. The iterative run in O(log(n)) and use O(1) memory. While, the recursive one run in O(log(n)) and use O(log(n)) memory because you keep push high and low into the stack.

Edited by invisal
Member Avatar for JamesCherrill

the recursive one run in O(log(n)) and use O(log(n)) memory because you keep push high and low into the stack.

Not necessarily. This is a case of tail recursion, so there's no need to consume stack for each call. Some compilers will automatically optimise the call/stack allocation out and replace it with effectively a simple goto (although sadly the current Oracle Java compiler isn't one of those).

See http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044

Edited by JamesCherrill
commented: Good point for mention about "tail recursion". +9
Member Avatar for invisal

(I was meant to post this as comment, but because it is too long so I will make a reply)

To be precise, tail recursion optimization is the process of defining recursive code that can be efficiently turn to iterative code. So in theory, the recursive binary search takes O(log(n)) memory. In practice, some compilers are smart enough to turn the recursive binary search to iterative binary search.

commented: OK, yes. +15
commented: I though tail recursion is not allowed in java. Am i correct? +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.