code 1

class Solution {
  public:
  int helper(int arr[],int n , int k , int l , int r){
      
        // int mid = (l r)/2;
        int mid = l (r-l)/2;
        
        if(l>=r ){
            
            return -1;
            
            
        }
        
        if(arr[mid]==k){
            return mid;
            
        }       
        else if(arr[mid]<k){
            l = mid 1;
            
            
        }
        else{
            r = mid;
            
        }
        return helper(arr,n,k,l,r);
  }
  
  
    int binarysearch(int arr[], int n, int k) {
       
        
        return helper(arr,n,k,0,n-1);
        
        
        
    }

code 2

class Solution {
  public:
    int binarysearch(int arr[], int n, int k) {
        int low=0;
        int high=n-1;
        int mid=low (high-low)/2;
        
        while(low<=high){
            if(arr[mid]==k){
                return mid;
        }
        else if(arr[mid]<=k){
            low=mid 1;
        }
        else{
            high=mid-1;
        }
        mid=low (high-low)/2;
    }
    if(k!=arr[mid]){
        return -1;
    }
    else{
        return mid;
    }
    }
};

while submitting for large amount of testcases the code 1 does not work while code 2 works fluently without any errors, i know that recursion is being used in code 1 but that must work right??

i tried changing the "r = mid " to "r = mid -1" but it did'nt worked too

CodePudding user response：

There are two things to mention about your code (first version):

Your check that l>=r comes before you have checked that maybe l and r are equal and arr[l] is the value you are looking for. When l and r are equal, you should not bail out with return false yet.

Instead, return false when l>r, because that means the range is empty.

Secondly, r = mid is not reducing the range enough. By the time execution gets there, it has already been asserted that the searched element is not at index mid, so mid can be excluded from the range that you pass to the recursive call. So do:

r = mid-1;

Here is your code with those two corrections:

int helper(int arr[],int n , int k , int l , int r){
    if(l>r ){ // <--
        return -1;
    }
    int mid = l (r-l)/2;
    if(arr[mid]==k){
        return mid;
    }       
    else if(arr[mid]<k){
        l = mid 1;
    }
    else{
        r = mid-1; // <-- 
    }
    return helper(arr,n,k,l,r);
}