C#•2y ago

✅ Comprehension questions (LeetCode Binary Search)

Like the title says it's about this puzzle https://leetcode.com/problems/binary-search/description/ I am analysing a couple of solutions submitted on the site One of the things that caught my attention is as follows: in an iterative solution there is no return statement in the if-block like this:

while(l<=r){
            int m=l+(r-l)/2;
            if(nums[m]==target)
                return m; //returns only here
            else if(nums[m]>target)
                r=m-1; //no return statement in this block
            else
                l=m+1; //here no return either. why??
        }

while(l<=r){
            int m=l+(r-l)/2;
            if(nums[m]==target)
                return m; //returns only here
            else if(nums[m]>target)
                r=m-1; //no return statement in this block
            else
                l=m+1; //here no return either. why??
        }

` Any recursive solution I saw does return the recursion method however:

if (min > max)
        {
            return -1;
        }
        else
        {
            int mid = (min + max) / 2;
            if (target == inputArray[mid])
            {
                return mid;
            }
            else if (target < inputArray[mid])
            {
                return BinarySearchRecursive(inputArray, target, min, mid - 1); //returns the recursive method. why? 
            }
            else
            {
                return BinarySearchRecursive(inputArray, target, mid + 1, max); //here also. why?
            }
        }

if (min > max)
        {
            return -1;
        }
        else
        {
            int mid = (min + max) / 2;
            if (target == inputArray[mid])
            {
                return mid;
            }
            else if (target < inputArray[mid])
            {
                return BinarySearchRecursive(inputArray, target, min, mid - 1); //returns the recursive method. why? 
            }
            else
            {
                return BinarySearchRecursive(inputArray, target, mid + 1, max); //here also. why?
            }
        }

` Could anyone kindly tell me why it is like this?

LeetCode

Binary Search - LeetCode

Can you solve this real interview question? Binary Search - Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. Example 1: Input: num...

5 Replies

Angius•2y ago

A recursive method has to use its own return value, so it has to return something

morry329#OP•2y ago

Ok I got it 🙂 And why does an iterative method have to return nothing ? You see, I have some gaps in understanding this 😅

Angius•2y ago

Well, it might need to return something at the end But it could also Console.Write() the result Or use an out parameter, or a ref, or any number of other things

Anton•2y ago

it returns the value at the current index after the loop, supposedly ah no, it returns in the loop see the second statement in the loop if it doesn't return, it loops again and again, until it does if you returned later too, the loop would've been pointless

morry329#OP•2y ago

Ahh I got it! Thanks for the clarification @AntonC @Angius

Gaming

Programming

✅ Comprehension questions (LeetCode Binary Search)