Guest User

Untitled

a guest
Sep 11th, 2019
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Arrays;
  2.  
  3. public class TAddi_HW1 {
  4.  
  5. public static void main(String[] args) {
  6. int size = 10;
  7.  
  8. while(size <= 100000) {
  9. int[] array = new int[size];
  10.  
  11. for (int i = 0; i < size; i++) {
  12. array[i] = (int) (1 + Math.random() * 100000);
  13. }
  14.  
  15. for (int j = 1; j < array.length; j++) {
  16. for (int k = 0; k < array.length - 1; k++) {
  17. if (array[k] > array[k + 1]) {
  18. int temp = array[k + 1];
  19. array[k + 1] = array[k];
  20. array[k] = temp;
  21. }
  22. }
  23.  
  24. }
  25.  
  26. int target = (int) (1 + Math.random() * 100000);
  27.  
  28. System.out.println("Linear Search:");
  29.  
  30. long T1 = System.nanoTime();
  31. boolean index = linearSearch(array, target);
  32. long T2 = System.nanoTime();
  33. long time = T2 - T1;
  34. if (index == false) {
  35. System.out.printf("In an array of input size " + size + ", %d is not found in array %n", target);
  36. } else {
  37. System.out.printf("In an array of input size " + size + ", %d is found in array %n", target);
  38. }
  39. System.out.println("Recorded Time: " + time);
  40. System.out.println();
  41.  
  42. System.out.println("Binary Search:");
  43.  
  44. T1 = System.nanoTime();
  45. index = BinarySearch(array, target);
  46. T2 = System.nanoTime();
  47. time = T2 - T1;
  48. if (index == false) {
  49. System.out.printf("In an array of input size " + size + ", %d is not found in array %n", target);
  50. } else {
  51. System.out.printf("In an array of input size " + size + ", %d is found in array %n", target);
  52. }
  53. System.out.println("Recorded Time: " + time);
  54. System.out.println();
  55. size = size * 10;
  56. }
  57. }
  58.  
  59. public static boolean BinarySearch(int[] array, int target) {
  60. int low = 0;
  61. int high = array.length - 1;
  62.  
  63. while (high >= low) {
  64. int middle = (low + high) / 2;
  65. if (array[middle] == target) {
  66. return true;
  67. } else if (array[middle] < target) {
  68. low = middle + 1;
  69. } else if (array[middle] > target) {
  70. high = middle - 1;
  71. }
  72. }
  73. return false;
  74. }
  75.  
  76.  
  77.  
  78. public static boolean linearSearch(int[] array, int target) {
  79.  
  80. for (int i = 0; i < array.length; i++) {
  81. if (array[i] == target) {
  82. return true;
  83. }
  84. }
  85. return false;
  86. }
  87.  
  88. }
RAW Paste Data