while coding for binary search using recursion i faced some doubts

Viewed 49

When using only if, I had to return some integer

public class solution {
    
    public static int binarySearch(int arr[], int x,int si,int ei){
        if(si>ei){
            return -1;
        }
        int mid=(si+ei)/2;
        if(arr[mid]==x){
            return mid;
        }
        if(arr[mid]>x){
           return binarySearch(arr,x,si,mid-1);
        }
        if(arr[mid]<x){
           return binarySearch(arr,x,mid+1,ei);
        }
        return 0;
    }

   
}

but when using if-else-if, I don't have to return any integer, why?

public class solution {
    
    public static int binarySearch(int arr[], int x,int si,int ei){
        if(si>ei){
            return -1;
        }
       
        int mid=(si+ei)/2;
        if(arr[mid]==x){
            return mid;
        }
        else if(arr[mid]>x){
           return binarySearch(arr,x,si,mid-1);
        }
        else {
           return binarySearch(arr,x,mid+1,ei);
        }
    }
}
4 Answers

When a method has return type in signature, something should be returned from the method in all condition. And that check is made at compile time in Java.

When you use if in your code logically that condition can be true or false. If that's true the method will get something returned from if block. But if the condition is false, method won't get anything to return back (because code inside if condition in not executed). So in that case method need something to return as default when if condition is resulted as false. From first method if all if conditions like

        if(si>ei){
            return -1;
        }
        int mid=(si+ei)/2;
        if(arr[mid]==x){
            return mid;
        }
        if(arr[mid]>x){
           return binarySearch(arr,x,si,mid-1);
        }
        if(arr[mid]<x){
           return binarySearch(arr,x,mid+1,ei);
        }

are false. Method won't be in situation to return anything.

On the other place when you use else with if (weather it is if-else or if-elseIf-else) then condition when if is false (or elseIf is false), the else part will return something from method. So always there will be something to return from method. In second method like

if(arr[mid]==x){
        return mid;
    }
   else if(arr[mid]>x){
       return binarySearch(arr,x,si,mid-1);
    }
   else
       return binarySearch(arr,x,mid+1,ei);
   }

if the first if condition is true mid will be returned. If arr[mid]>x is true binarySearch(arr,x,si,mid-1); result will be returned. If both are true else will always be there to return something (in your case binarySearch(arr,x,mid+1,ei);).

The compiler can not guess that the last if condition will always be true. So you have to provide a return value in case it is false. Even though it will never happen. You could even get rid of the last if statement.

    public class solution {
    
    public static int binarySearch(int arr[], int x,int si,int ei){
        if(si>ei){
            return -1;
        }
        int mid=(si+ei)/2;
        if(arr[mid]==x){
            return mid;
        }
        if(arr[mid]>x){
           return binarySearch(arr,x,si,mid-1);
        }
        return binarySearch(arr,x,mid+1,ei);
    }

   
}

Because all possible outcomes of your second method's work will return something. You always need to ensure that when your method is not void.

In first case you need to specify return value for the case, when none of your three if statements' conditions is true.

    if(arr[mid]==x){
        return mid;
    }
    if(arr[mid]>x){
       return binarySearch(arr,x,si,mid-1);
    }
    if(arr[mid]<x){
       return binarySearch(arr,x,mid+1,ei);
    } 

However, it is clear to see that you will never face a situation, when all the above conditions are false, but compiler cannot figure this out, so you need to design your code that way, in which compiler will know that in all possible conditions your method will return value. So the second implementation is more "clean" and logically correct

you have set the return type to int. When you are using if statements, there is no surety that one of the if statements has to work and you will get the return value.

if()
{
   return value;
}
if()
{
   return value;

}

In the above code both ifs can work or both can not work if conditions are not satisfied. therefore it might be possible that we will not get a return value.

and in else if, else case we have surety that one of the case will definitely work and we will get a return value 100%

if()
{
   return value;
}
else if()
{
   return value;
}
else{
   return value;
}

in the above code only one of the if condition will work and we will always get a return value.

Related