Join the social network of Tech Nerds, increase skill rank, get work, manage projects...

• # Can someone explain the algorithm of this java program?

• 0
• 0
• 0
• 1
• 0
• 0
• 0
• 178

I found it in the net and I want to know the explanation of it's algorithm. I'm having a hard time to understand this. thank you so much :)

``````import java.util.Scanner;
class BinarySearch
{
public static void main(String args[])
{
int c, first, last, middle, n, search, array[];

Scanner in = new Scanner(System.in);
System.out.println("Enter number of elements");
n = in.nextInt();
array = new int[n];

System.out.println("Enter " + n + " integers");

for (c = 0; c < n; c++)
array[c] = in.nextInt();

System.out.println("Enter value to find");
search = in.nextInt();

first  = 0;
last   = n - 1;
middle = (first + last)/2;

while( first <= last )
{
if ( array[middle] < search )
first = middle + 1;
else if ( array[middle] == search )
{
System.out.println(search + " found at location " + (middle + 1) + ".");
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
if ( first > last )
System.out.println(search + " is not present in the list.\n");
}
}``````

• over 3 years ago

The program which you have given performs the binary search on the given element.

Binary Search

This is one of the searching algorithms with the complexity of (log n).It is based on the principle of divide and conquer. Data should be in sorted form for this algorithm to work.

It searches the middle element first. If the desired element is found, then it returns that element. If the middle element is greater than that element than the search is performed if the left sub-array or else it is performed on the right sub-array.

How it works?

The first condition is that the array should be in the sorted form. We'll see it with the help of example in which we will search for 17 in the given array.

3 6 8 9 11 12 14 17 20 65

1) We calculate the middle of the array with the formula:

middle = (low + high) / 2
low= lower index of the array which is 0 in this.
high= higher index of the array which is 9.
Here it is, (0 + 9) / 2 = 4 (int value of 4.5).
so 4 is the middle index value over here.

3 6 8 9 11 12 14 17 20 65

The value at 4th index is 11.

Now we compare 11 with our value being searched. i.e. 17 . Both the values doesn't match. Now we will compare both of them and since 11 < 17 that means our value will be found if the right sub array

For that, we change our low to middle+1 and repeat the same thing again.

low = mid + 1 middle = (low + high) / 2 So this is the new array.

3 6 8 9 11

12 14 17 20 65

middle= (5+9)/2 = 7th position. Our new mid is 17 now.

Now we will again compare the value we need to search with this value. Since the value matches we will return the position of the element.

i.e middle+1 which is (7+1)=8.

So it will return that "element is found at 8th position".

If still it would have not found then we will keep repeating the same thing till our value is being found and if not found we return the appropriate message for that.

This search technique is better than linear search because it reduces the number of comparasions that needs to be done to find the given item in the array.

OR
OR
Register

OR
Fill out the form below and instructions to reset your password will be emailed to you:

• Hire
• Post Projects

### Post Projects

• All at 0 Cost ....
• Post Tech Job
• Select Best Bidder
• Track the Project
• Approve Work and Pay safely
• Browse Nerds
• Work
• Find Projects Find Projects
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Manage
• Company Company

### Manage Company

• All at 0 Cost ....
• Manage Company and Employee Profiles
• Company wide Employee Productivity Reports
• Knowledge Sharing and Collaboration Tools
• Get Sales Lead and Bid for Tech Projects
• Send Invoices and Receive Payment Safely
• Learn
• Nerd Digest Nerd Digest
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Tech Q & A Tech Q & A
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General