An array problem involving a recursive binary search

  • #1
Summary:: I have to solve this problem stirctly according to the question that follows:

Mentor note: I edited the original code to add indentation and a few blank lines to make the code more readable, so line 43 is no longer the line in question.
so this is the question i tried but it gives error in line 43 of my program it is only when the element to be searched is not present int the array while it must print "ELEMENT NOT FOUND "message if the element is absent .
foollowing is my program and output.
Java:
import java.io.*;
class Binsearch
{
  int arr[];
  int n;
  static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  Binsearch(int nn)
  {
    n=nn;
    arr=new int[nn];
  }

  void fillarray()throws IOException
  {
    System.out.println("ENTER THE ELEMENTS OF ARRAY");
    for(int i=0;i<n;i++)
    {
      arr[i]=Integer.parseInt(br.readLine());
    }
  }                //end of method

  void sort()
  {
    int temp=0;
    for(int i=0;i<n;i++)
      {
        for(int j=0;j<n-1;j++)
        {
          if(arr[j]>arr[j+1])
         {
            temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
         }
       }
    }
  }

  int bin_search(int l,int u,int v)
  {
    int m=(l+u)/2;
    System.out.println("m="+m+"l="+l+"u="+u+"v="+v);
    if(arr[m]==v)
      return(m);
    else if(arr[m]>v)
      return(bin_search(0,m,v));
    else if(arr[m]<v)
      return(bin_search(u,m,v));
    else
      return(-1);
  }

  public static void main(String args[])throws IOException
  {
    System.out.println("ENTER THE NUMBER OF ELEMENTS");
    Binsearch ob=new Binsearch(Integer.parseInt(br.readLine()));
    ob.fillarray();
    ob.sort();
    System.out.println("ENTER THE NUMBER TO BE SEARCHED");
    int r=0;
    r=ob.bin_search(0,ob.n,Integer.parseInt(br.readLine()));
    System.out.println("THE SORTED ARRAY IS:");
    for(int i=0;i<ob.n;i++)
      System.out.print(ob.arr[i]+"\t");
    System.out.println();
    System.out.println("THE VALUE OF R IS:"+r);
    if(r==-1)
    {
      System.out.println("ELEMENT NOT FOUND");
    }
    else
    {
      System.out.println("ELEMENT FOUND AT "+r);
    }
  }                                        //end of main
}


and the output
1601492470742.png
[/code]
 

Attachments

Last edited by a moderator:

Answers and Replies

  • #2
Filip Larsen
Gold Member
1,296
222
What will your bin_search method do if it is called with lower == upper when array[lower] != v?

Hint:
a stack trace like the one you see for your program (triggered by a StackOverflowError no doubt) is a sure indication of infinite recursion, typically due to wrong or missing stop condition.
 
  • #3
34,275
5,912
Your bin_search() function needs to be able to determine whether a particular element it's searching for isn't actually in the list. If you narrow the search down to the values between arr[m - 1] and arr[m + 1], and the value searched for isn't either of these values or arr[m], then the element isn't in the array. I don't think your function is doing this.

BTW, your parameter names really need some work.
Java:
int bin_search(int l,int u,int v)
Single-letter names are a terrible idea. What are l, u, and v supposed to represent?
 
  • #4
1,544
1,420
I make an assumption: in the method bin_search(...), l means lower limit, u means upper limit, and v means the value to be searched for.

There are problems in current line 46 and 48 in your code.

In line 46, you write:
return(bin_search(0,m,v)); Why pass m as the upper limit? This line is reached only if arr[m] != v. Therefore, you should pass m-1 as the upper limit.

In line 48, you write bin_search(u,m,v); This should be bin_search(m+1,u,v). Any idea why?
 
Last edited:
  • #5
If you narrow the search down to the values between arr[m - 1] and arr[m + 1], and the value searched for isn't either of these values or arr[m], then the element isn't in the array. I don't think your function is doing this.
yes.thanks i was missing that point. i tried it that way and figured that it was executing infinitely . so i modified the function .
Java:
import java.io.*;
class Binsearch
{
int arr[];
int n;
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Binsearch(int nn)
{
n=nn;
arr=new int[nn];
}
void fillarray()throws IOException
{
System.out.println("ENTER THE ELEMENTS OF ARRAY");
for(int i=0;i<n;i++)
{
arr[i]=Integer.parseInt(br.readLine());
}
}                //end of method
void sort()
{
int temp=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
int bin_search(int l,int u,int v)
{
if(l<u)                        //I ADDED THIS CONDITION TO PREVENT INFINITE EXECUTION
{
int m=(l+u)/2;
System.out.println("m="+m+"l="+l+"u="+u+"v="+v);
if(arr[m]==v)
return(m);
else if(arr[m]>v)
return(bin_search(0,m-1,v));
else if(arr[m]<v)
return(bin_search(m+1,u,v));
}
else                        //HERE'S THE ELSE  STATEMENT
return(-1);
}                        //giving error here line 51
public static void main(String args[])throws IOException
{
System.out.println("ENTER THE NUMBER OF ELEMENTS");
Binsearch ob=new Binsearch(Integer.parseInt(br.readLine()));
ob.fillarray();
ob.sort();
System.out.println("ENTER THE NUMBER TO BE SEARCHED");
int r=0;
r=ob.bin_search(0,ob.n,Integer.parseInt(br.readLine()));
System.out.println("THE SORTED ARRAY IS:");
for(int i=0;i<ob.n;i++)
System.out.print(ob.arr[i]+"\t");
System.out.println();
System.out.println("THE VALUE OF R IS:"+r);
if(r==-1)
{
System.out.println("ELEMENT NOT FOUND");
}
else
{
System.out.println("ELEMENT FOUND AT "+r);
}
}                                        //end of main
}
But now it's giving another error of missing return statement although i've closed the braces and written the return statement in correct syntax.
Kindly help figure out the mistake
Single-letter names are a terrible idea.
Sorry but we can't modify the parameters given in the question.
And i wanted to ask that Are programs with lesser data members considered more accurate?
does it have anything to do with it's efficiency?
What are l, u, and v supposed to represent?
l=lower value of index i.e.,0
u=upper vale of index i.e., arr.length-1
and v contains the number to be searched
 
Last edited by a moderator:
  • #6
34,275
5,912
But now it's giving another error of missing return statement although i've closed the braces and written the return statement in correct syntax.
Kindly help figure out the mistake
Your code is very difficult to read, since it has every line jammed up against the left margin. I went through the code you had in post #1, and indented it to make it more readable.
Single-letter names are a terrible idea.
Sorry but we can't modify the parameters given in the question.
Really? Are you saying that your instructor will mark your program down if you use parameter names that are more understandable as to what they're being used for? I find that really hard to believe. No reasonable instructor would mark down for using parameter names that make it clear what they are to be used for.

I see that you changed the name of one method to fillarray(). In the program statement, it was fillaray, in which "aray" is the misspelled version of "array".

And i wanted to ask that Are programs with lesser data members considered more accurate?
does it have anything to do with it's efficiency?
What do you mean by "lesser data members"? Are you talking about the difference in function parameter names? The name of a variable or function parameter has absolutely nothing to do with efficiency.
 
  • #7
1,544
1,420
Really? Are you saying that your instructor will mark your program down if you use parameter names that are more understandable as to what they're being used for? I find that really hard to believe. No reasonable instructor would mark down for using parameter names that make it clear what they are to be used for.
By some pure coincidence, I had solved that exact question (which the OP has posted) back in high school. I am guessing that the OP is from the same country as me. Here, instructors are unreasonable, and they will not allow you to change the parameters that are defined in the question. If parameter names are changed, the student's marks are deducted for not following the question. Awkward, but true!

@anyonebutangel which IDE are you using for writing the programs?
 
  • #8
34,275
5,912
Here, instructors are unreasonable, and they will not allow you to change the parameters that are defined in the question. If parameter names are changed, the student's marks are deducted for not following the question. Awkward, but true!
That is ridiculous, pedantic, and completely unreasonable!
I wonder if the instructor will deduct points for changing the name of fillaray to the name that the OP is using, fillarray? I deduct points from students if the change the names of functions, but I don't care about the parameter names, as long as they are informative names.

@anyonebutangel, I don't see anything wrong with your bin_search() method that would cause a missing return statement error. Are you sure that the code you showed here is the same as the code that the compiler sees?
 
  • #9
1,544
1,420
That is ridiculous, pedantic, and completely unreasonable!
True, but that's the reality unfortunately.
I wonder if the instructor will deduct points for changing the name of fillaray to the name that the OP is using, fillarray? I deduct points from students if the change the names of functions, but I don't care about the parameter names, as long as they are informative names.
If this question comes in an exam, then you are supposed to follow the question word by word. That means students are supposed to use misspelled function names. If, however, the question is given as a part of a project (like it was in my case), then one can usually have a word with the teacher about this. If a change has to be made, it has to be made for the whole class.
 
  • #10
Filip Larsen
Gold Member
1,296
222
But now it's giving another error of missing return statement although i've closed the braces and written the return statement in correct syntax.
Check your if statements around line 47.
 
  • #11
guys i designed another program with same method(int bin_search).once I get the cause for error,i'll change it in the main program.have a look.
1601629063374.png




i hope it"s easier to read.and i Still can't get it where the problem is.
Are you sure that the code you showed here is the same as the code that the compiler sees?
yes.I have only one file with that name and also for execution i'm entering the path of file for compilation .so yes i"m executing same file.
which IDE are you using for writing the programs?
I 'm using JDK1.5 compiler.
 
Last edited:
  • #12
34,275
5,912
i hope it"s easier to read
No, it's not easier to read.
1) Half of the screen shot is taken up by the 5 or 6 lines in the command prompt window. It's much better to enter the program code as text, using code tags (as I used on your code in post #1, and have used in the snippet below).
2) )Your code has no indentation, which makes it much harder to understand your program structure

Rather than starting again from scratch, why not fix what's wrong with the code you started with?
 
Last edited:
  • #13
<Post edited to remove a quote of mine (Mark44) that was in error.>
But I'm not able to figure out why is it giving "missing return statement".
 
Last edited by a moderator:
  • #14
1,544
1,420
I 'm using JDK1.5 compiler.
That's not the answer to my question. I asked which IDE (Integrated Development Environment) are you using, not which compiler you are using? Your answer should be "none", because you are using Notepad. Java IDEs include BlueJ, NetBeans and Intellij IDEA.
yeah i get that.But I'm not able to figure out why is it giving "missing return statement".
Look at this portion of the code that you posted earlier:
Java:
int m=(l+u)/2;
System.out.println("m="+m+"l="+l+"u="+u+"v="+v);
if(arr[m]==v)
    return(m);
else if(arr[m]>v)
    return(bin_search(0,m-1,v));
else if(arr[m]<v)
    return(bin_search(m+1,u,v));
Your if-else conditions include equal to, less than and greater than v. Fine, that covers all the cases possible. But the compiler doesn't understand that. It is asking you: what if none of the above conditions are met? The compiler doesn't know that there can be no other condition. The solution is to simply change one else if to else.

I have some advice for you:

1. Please indent your code. We are not concerned about who has taught you to write code without indentation; our point is that this is simply the wrong practice. In longer programs, if you write code without indentation, you are going to have a very bad time dealing with errors. If you ever have to work with Python, you will face an even harder time because your code just won't compile without indentation.

2. Please use a proper IDE for writing programs. My first choice would have been NetBeans (and not BlueJ) due to its simplicity. Errors like the one you are getting (missing return statement) would have been pointed out by the IDE itself even before you compiled your program.

Edit: spelling.
 
Last edited:
  • Love
Likes Mark44
  • #15
34,275
5,912
But the compiler doesn't understand that. It is asking you: what if none of the above conditions are met? The compiler doesn't know that there can be no other condition. The solution is to simply change one else if to else.
Very good point, and one that I didn't consider, as I was focused on the statements in the if and else if clauses.
 
  • Like
Likes Wrichik Basu
  • #16
Hey guys ,Figured out.
If you want to have a look

Java:
class search
{
     int arr[]={25,81,101,56,24};
    int bin_search(int lower,int upper,int v)
      {
      int middle=(lower+upper)/2;
            if(upper<lower)
                 return(-1);
           else if(arr[middle]==v)
                 return(middle);
         else if(arr[middle]>v)
                  return(bin_search(lower,middle-1,v));
         else
                 return(bin_search(middle+1,upper,v));
        }
public static void main(String args[])
       {
           search ob=new search();
           int result=ob.bin_search(0,4,50);
           if(result==-1)
                   System.out.println("ELEMENT NOT PRESENT");
           else
                 System.out.println("ELEMENT FOUND AT"+result);
                result=ob.bin_search(0,4,101);
           if(result==-1)
                  System.out.println("ELEMENT NOT PRESENT");
          else
                   System.out.println("ELEMENT FOUND AT"+result);
         }
}
1601650553684.png



THANK YOU
 
Last edited:
  • #17
34,275
5,912
Much better! Your code is in code tags, it's indented, and you have informative variable names. All of those make it easier for people to read and understand your code, and to provide whatever help might be needed.
 
  • Like
Likes anyonebutangel
  • #18
1,544
1,420
Hey guys ,Figured out.
If you want to have a look

Java:
class search
{
     int arr[]={25,81,101,56,24};
    int bin_search(int lower,int upper,int v)
      {
      int middle=(lower+upper)/2;
            if(upper<lower)
                 return(-1);
           else if(arr[middle]==v)
                 return(middle);
         else if(arr[middle]>v)
                  return(bin_search(lower,middle-1,v));
         else
                 return(bin_search(middle+1,upper,v));
        }
public static void main(String args[])
       {
           search ob=new search();
           int result=ob.bin_search(0,4,50);
           if(result==-1)
                   System.out.println("ELEMENT NOT PRESENT");
           else
                 System.out.println("ELEMENT FOUND AT"+result);
                result=ob.bin_search(0,4,101);
           if(result==-1)
                  System.out.println("ELEMENT NOT PRESENT");
          else
                   System.out.println("ELEMENT FOUND AT"+result);
         }
}
Good job indenting the code, but please follow a specific indentation pattern. For example, lines 6, 7, 9, 11 and 14 should be at the same level of indentation. Same for lines 4 and 16.

By the way, the following is a better version of the bin_search method:
Java:
int bin_search(int lower,int upper,int v) {
      int middle = (lower + upper) / 2;

      if (upper < lower) {
          return -1;
      }
      else {
          if (arr[middle] == v)
              return middle;
          else if (arr[middle] > v)
              return bin_search(lower,middle - 1, v);
          else
              return bin_search(middle + 1, upper, v);
      }
}
 
Last edited:
  • #19
please follow a specific indentation pattern.
o.k i'll keep in mind.
thanks
 
  • Like
Likes Wrichik Basu

Related Threads on An array problem involving a recursive binary search

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
3K
Replies
0
Views
6K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
859
Replies
3
Views
4K
Replies
11
Views
5K
  • Last Post
Replies
0
Views
1K
Replies
5
Views
2K
Top