An array problem involving a recursive binary search

In summary: String args[])throws IOException{System.out.println("ENTER THE NUMBER OF ELEMENTS");Binsearch ob=new Binsearch(Integer.parseInt(br.readLine()));ob
  • #1
anyonebutangel
40
5
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

  • 1601490245936.png
    1601490245936.png
    13.3 KB · Views: 141
Last edited by a moderator:
Physics news on Phys.org
  • #2
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
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
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
Mark44 said:
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
anyonebutangel said:
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.
Mark44 said:
Single-letter names are a terrible idea.
anyonebutangel said:
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".

anyonebutangel said:
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
Mark44 said:
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
Wrichik Basu said:
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
Mark44 said:
That is ridiculous, pedantic, and completely unreasonable!
True, but that's the reality unfortunately.
Mark44 said:
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
anyonebutangel said:
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.
Mark44 said:
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.
Wrichik Basu said:
which IDE are you using for writing the programs?
I 'm using JDK1.5 compiler.
 
Last edited:
  • #12
anyonebutangel said:
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
anyonebutangel said:
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.
anyonebutangel said:
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
Wrichik Basu said:
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
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
anyonebutangel said:
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
Wrichik Basu said:
please follow a specific indentation pattern.
o.k i'll keep in mind.
thanks
 
  • Like
Likes Wrichik Basu

1. What is a recursive binary search?

A recursive binary search is a searching algorithm that divides a sorted array into two halves and recursively searches through each half until the target element is found. It is a more efficient way of searching through a large array compared to linear search.

2. How does a recursive binary search work?

A recursive binary search works by taking the middle element of the array and comparing it to the target element. If the middle element is equal to the target, the search is complete. If the middle element is greater than the target, the search continues in the first half of the array. If the middle element is less than the target, the search continues in the second half of the array. This process is repeated until the target element is found or the array is exhausted.

3. What is the time complexity of a recursive binary search?

The time complexity of a recursive binary search is O(log n), where n is the size of the array. This means that the time it takes to search through the array increases at a slower rate as the size of the array increases, making it a more efficient algorithm compared to linear search.

4. What are the advantages of using a recursive binary search?

One advantage of using a recursive binary search is its efficiency in searching through large arrays. It also requires less code compared to other searching algorithms, making it easier to implement. Additionally, it can be used for both sorted and unsorted arrays, as long as the array is divided into two halves each time.

5. What are the potential drawbacks of a recursive binary search?

One potential drawback of a recursive binary search is that it requires the array to be sorted beforehand. If the array is not sorted, the algorithm will not work correctly. Additionally, it may not be the best choice for searching through small arrays, as the time complexity may not make a significant difference compared to linear search.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
4
Views
914
  • Engineering and Comp Sci Homework Help
Replies
3
Views
739
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
21
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
17
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
12
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Back
Top