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

  • Can someone explain the algorithm of this java program?

    @MewYan
    Recommendations Offline Message

    • 0
    • 0
    • 0
    • 1
    • 0
    • 0
    • 0
    • 401
    Answer it

    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");
  }
 }
    Java Binary Search Algorthim
    Answer it

 1 Answer(s)

  • @akashb1992
    Recommendations Offline Message

    almost 9 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.

Sign In
Forgot Password?
                           OR                           
Create an account !!
                           OR                           
Register

Sign up using

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