Explore Westonci.ca, the premier Q&A site that helps you find precise answers to your questions, no matter the topic. Connect with a community of experts ready to help you find accurate solutions to your questions quickly and efficiently. Connect with a community of professionals ready to provide precise solutions to your questions quickly and accurately.
Sagot :
CASE1: If target is equal to middle, then return mid.
CASE2:If target is less than middle i.e., target<A[mid],we discard all the elements in the right search space including mid element. Now our new high would be mid-1 while 'low' remains as it is.
CASE3:If the target element is greater than middle i.e., target>A[mid],we discard all the elements in the left search space including mid element. Now our new low would be mid+1 while 'high' remains as it is.
What is Recursive Algorithm?
Recursive algorithm, a function calls itself again and again till the base condition(stopping condition) is satisfied.
Let us track the search space by using two index start and end. Initialy low=0 and high=n-1(as initialy whole array is search space).At each step, we find mid value in the search space and compare it with target value. There are three cases possible:
CASE1: If target is equal to middle, then return mid.
CASE2:If target is less than middle i.e., target<A[mid],we discard all the elements in the right search space including mid element. Now our new high would be mid-1 while 'low' remains as it is.
CASE3:If the target element is greater than middle i.e., target>A[mid],we discard all the elements in the left search space including mid element. Now our new low would be mid+1 while 'high' remains as it is.
- Recursive implementation of binary search algorithm, in the method binarySearch(), follows almost the same logic as iterative version, except for a couple of differences.
- The first difference is that the while loop is replaced by a recursive call back to the same method with the new values of low and high passed to the next recursive invocation along with "Array" and "key" or target element.
- The second difference is that instead of returning false when the while loop exits in the iterative version, in case of the recursive version, the condition of low > high is checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning false.
- Also, note that the recursive invocations of binarySearch() return back the search result up the recursive call stack so that true or false return value is passed back up the call stack without any further processing.
To learn more about binarySearch:
https://brainly.com/question/29487950
#SPJ4
Thanks for stopping by. We are committed to providing the best answers for all your questions. See you again soon. We hope you found what you were looking for. Feel free to revisit us for more answers and updated information. We're glad you visited Westonci.ca. Return anytime for updated answers from our knowledgeable team.
