Welcome to Westonci.ca, your one-stop destination for finding answers to all your questions. Join our expert community now! Join our platform to connect with experts ready to provide detailed answers to your questions in various areas. Experience the convenience of finding accurate answers to your questions from knowledgeable experts on our platform.
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 using our platform. We're always here to provide accurate and up-to-date answers to all your queries. Thanks for using our service. We're always here to provide accurate and up-to-date answers to all your queries. We're glad you chose Westonci.ca. Revisit us for updated answers from our knowledgeable team.
