Monday, 8 June 2015

Program to implement Binary search

//Program to implement Binary Search
import java.io.*;
public class Binary
{
  public static void main(String args[]) throws Exception
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n, item, i, j, mid, top, bottom;
    int a[] = new int[100];

    System.out.print("Enter number of elements: ");
    n = Integer.parseInt(br.readLine());

    System.out.println("Enter "+n+" elements in ascending order: ");
    for (i = 0; i <= (n-1); i++) 
    {
      a[i]=Integer.parseInt(br.readLine());
    }

    System.out.print("\nEnter the element to search: ");
    item=Integer.parseInt(br.readLine());

    bottom = 0;
    top = n; 
    do 
    {
      mid = (bottom + top) / 2;
      if (item < a[mid])
      {
        top = mid - 1;
      }
      else if (item > a[mid])
      {
        bottom = mid + 1;
      }
    }while(item != a[mid] && bottom <= top);
     
    if (item == a[mid]) 
    {
      System.out.print("\n"+item+" is found at position: "+(mid+1));
    } 
    else 
    {
      System.out.print("\n"+item+" is not found");
    }
    System.out.println();
  }
}
//Program to implement Binary search
import java.io.*;  
import java.util.*;
public class Binary  
{  
  public static void main(String args[]) throws Exception  
  {  
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        
    int n, item, i;    
        
    System.out.print("Enter number of elements: ");  
    n = Integer.parseInt(br.readLine());  

    int a[] = new int[n];
        
    System.out.println("Enter "+n+" elements: ");  
    for (i = 0; i <= (n-1); i++)   
    {  
      a[i]=Integer.parseInt(br.readLine());  
    }  
       
    Arrays.sort(a);
    System.out.println("\nThe sorted list:");
    for (i=0; i<=(a.length - 1); i++) 
    {
      System.out.println(a[i]+"\t");
    }
        
    System.out.print("\nEnter the element to search: ");  
    item=Integer.parseInt(br.readLine());  

    int retVal = Arrays.binarySearch(a,item);   
    System.out.println("The index of element "+item+": "+(retVal+1));

    System.out.println();  
  }  
}    
Output:
Enter number of elements: 5
Enter 5 elements:
3
5
9
1
2

The sorted list:
1
2
3
5
9

Enter the element to search: 5
The index of element 5: 4

No comments:

Post a Comment