m2skills

bsearch java

Mar 30th, 2017
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.18 KB | None | 0 0
  1. /**
  2.  * Created by MOHIT on 10-03-2017.
  3.  */
  4. import java.util.Scanner;
  5.  
  6. public class search {
  7.  
  8.     // static array to store elements
  9.     static int element[];
  10.  
  11.     public static void main(String arg[]) {
  12.  
  13.         Scanner sc = new Scanner(System.in);
  14.         // the following block takes comma seperated inputs and puts them into array
  15.         System.out.println("Enter the elements of the array : ");
  16.         String nums = sc.next();
  17.         String[] strArr = nums.split(",");
  18.         int size = strArr.length;
  19.         element = new int[size];
  20.         int i = 0;
  21.         for (String str2 :strArr) {
  22.             int temp = Integer.parseInt(str2);
  23.             element[i] = temp;
  24.             i++;
  25.         }
  26.        
  27.         // binary search requires the array to be sorted
  28.         // call to the sorting function
  29.         bubbleSort();
  30.        
  31.         // enter the number to be searched
  32.         System.out.println("\nEnter the number to be searched : ");
  33.         int num = sc.nextInt();
  34.  
  35.         // check if position is >= 0 then the element is found
  36.         int position = binarySearch(num);
  37.         if (position >= 0) {
  38.             System.out.println("Element found at position " + position);
  39.         } else {
  40.             System.out.println("Element not found in the array");
  41.         }
  42.     }
  43.  
  44.     // method that sorts the array using the bubble Sort algorithm
  45.     static void bubbleSort() {
  46.         int n = element.length;
  47.         for (int i = 0; i < n - 1; i++) {
  48.             for (int j = 0; j < n - 1; j++) {
  49.                 if (element[j] > element[j + 1]) {
  50.                     int temp = element[j];
  51.                     element[j] = element[j + 1];
  52.                     element[j + 1] = temp;
  53.                 }
  54.             }
  55.         }
  56.  
  57.         System.out.println("The sorted Array is : ");
  58.         for (int k:element) {
  59.             System.out.print(k + "  ");
  60.         }
  61.         return;
  62.     }
  63.  
  64.  
  65.     // method to search element using binary search algorithm
  66.     static int binarySearch(int num) {
  67.        
  68.         int low = 0, high = element.length - 1;
  69.         boolean found = false;
  70.         int position = 0;
  71.  
  72.         // loop till high is greater than low or till the element is not found
  73.         while (low <= high && found == false) {
  74.  
  75.             // calculate the mid value
  76.             int mid = (low + high) / 2;
  77.  
  78.             // compare the mid value with the element
  79.             // if equal then print the position and return
  80.             if (element[mid] == num) {
  81.                 position = mid;
  82.                 found = true;
  83.                 break;
  84.             }
  85.  
  86.             // else if the middle value if greater than the element
  87.             // then element lies on the left side of the mid so decrease high value
  88.             else if (element[mid] > num) {
  89.                 high = mid - 1;
  90.             }
  91.  
  92.             // else if the middle value if less than the element
  93.             // then element lies on the right side of the mid so increase low value
  94.             else if (element[mid] < num) {
  95.                 low = mid + 1;
  96.             }
  97.         }
  98.         // display this if element not found
  99.         if (found == false) {
  100.             return -1;
  101.         }
  102.         return position + 1;
  103.     }
  104.  
  105. }
Add Comment
Please, Sign In to add comment