What is the output of these commands? Java: Can someone please explain and help me with this task?

Question

Code:
public class Quest
{
public static int BS(int x, int[] a, int i, int j){
int m = (i+j)/ 2;
if (a[m] == x) return m;
if (i >= j) return -1;
if (a[m] > x) return BS(x, a, i, m);
else return BS(x, a, m + 1, j);
}
public static void main(String[] args) {
int[] array ={2, 9, 23, 25, 59, 65, 67, 89};
int N = Integer.parseInt(args[0]);

System.out.println(BS(N, array, 0, 7));

}
}

- What is the output of these commands?:
% java Quest 59
% java Quest 60

- What does the function BS() do?

I would highly appreciate if someone could help me here. I really don’t know what to do mostly because of the fact that I am new to this area

Answer 1

no. It will be 2 as array indexes start from 0
binary search can be confusing at first. Watch these (or if you find a better one, watch that. But seeing it visually will help)
This one explains binary search
https://youtu.be/JQhciTuD3E8
This one will explain what is happening in your code
https://youtu.be/T98PIp4omUA

Edit:
Belle
sorry, I though you asked about 23. Yes the output will be 3 for 25

Answer 2

There m=(i+j)/2
if a[m]==x ,then it return m.
Otherwise if a[m]>x, it means x may be in array between indexes i to m, (left array, and no need to search right array) else x is in from m+1 to j, (right side array, and no need to search left array)..
Note: list is already in sorted. (Must).

Sample are x=59 and 60 in the previous post.

Before reviewing code , read explanation of Binary search from link . you can understand it clearly...

Edit : Belle
For input 25, you get output 3
Since a[3]=25
You are giving input by command line argument arg[0]

Answer 3

I'm assuming you know the basics like functions, arrays in Java. If you don't I suggest you take it slow and first complete the Java course here on SoloLearn before revisiting this question.

So, as for th answer to question 2, the function BS() is an implementation of the binary search algorithm which searches for a element in a sorted array (or any other collection). I suggest you check this out
https://www.sololearn.com/learn/664/
or if it is unclear, just see some videos/articles on the topic

For the first question, the command
java Quest 59
in the shell, will execute the class file Quest and will pass 59 as the command line argument. The command line arguments are available as a String array passed to your main() function (the array `args`, in your case). So as 59 is passed in the the parameter, it is interpreted as an integer using the Integer.parseInt() method and assigned to N. Then, N is passed to the BS() function which then returns the first occurence of N in `array` and prints it. (same for 60)

Answer 4

That program is for Binary Search implementation.

For input java quest 59,
It does iteratively like initially, i=0,j=7, N=59 so m=3 a[3]>x (25>59) false so next do BS(59,a,4,7) and a[5]>x true so Calls BS(59,a,4,5) and returns m=4.(index value of input 59 in the array)

For java quest 60 returns -1 because it is not existing in list.
For input java quest 60,
It does iteratively like initially, i=0,j=7, N=60 so m=3 a[3]>x (25>60) false so next do BS(60,a,4,7) and a[5]>x true so Calls BS(60,a,4,5) and here i=4,j=5,m =4 . a[4]>60 false so calls BS(60,a,5,5) and i>=j true it means numbers is not in list so returns -1.

For more details refer this explanation.
Belle
Hope it helps.....
https://www.sololearn.com/learn/664/?ref=app

Answer 5

Belle
No.
% java Quest 59
will print the first occurence of 59 in `array`, or to be more precise, the index of `array` at which 59 is first found.

You can try the code yourself. Simply, change the line
`int N = .....`
to
`int N = <number-you-want-to-test>;`

Answer 6

okay, thank you both very very much!!! I truly appreciate both of your very helpful explanations and links!!

Answer 7

First of all, thank you for your answer!
Secondly you mean, that % java Quest 59 will print the frist component of „array“, so 2 and for % java Quest 60 as well?
Or did I misunderstood you?

Answer 8

thank you as well!
but why did you put for, I suppose m, 25? did you just chose a number from the array list?
And the 4 comes from m+1 right?
But what is with the 5? Wasn‘t j supposed to be 7?

Answer 9

So if I take the example % java Quest 25, will be the output 3?