Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.07 KB | None | 0 0
  1. // Java Program to illustrate reading from Text File
  2. // using Scanner Class
  3.  
  4. import java.io.*;
  5. import java.util.Hashtable;
  6. import java.util.Scanner;
  7.  
  8. public class Main {
  9.  
  10. // Returns index of x if it is present in arr[l..
  11. // r], else return -1
  12. static int binarySearch(int arr[], int l, int r, int x)
  13. {
  14. if (r >= l) {
  15. int mid = l + (r - l) / 2;
  16.  
  17. // If the element is present at the
  18. // middle itself
  19. if (arr[mid] == x)
  20. return mid;
  21.  
  22. // If element is smaller than mid, then
  23. // it can only be present in left subarray
  24. if (arr[mid] > x)
  25. return binarySearch(arr, l, mid - 1, x);
  26.  
  27. // Else the element can only be present
  28. // in right subarray
  29. return binarySearch(arr, mid + 1, r, x);
  30. }
  31.  
  32. // We reach here when element is not present
  33. // in array
  34. return -2;
  35. }
  36.  
  37. public static void main(String[] args) throws IOException {
  38.  
  39. // pass the path to the file as a parameter
  40. Scanner sc = new Scanner(new File("input.txt"));
  41.  
  42. int n;
  43. n = sc.nextInt();
  44. int arr[]=new int[n];
  45.  
  46. for (int i=0; i<n ;i++){
  47. arr[i] = sc.nextInt();
  48. }
  49. int m;
  50. m = sc.nextInt();
  51. int quers[] = new int[m];
  52.  
  53. // creating a hash table
  54. Hashtable<Integer, Integer> results =
  55. new Hashtable<>();
  56.  
  57. for (int i = 0; i < m; i++)
  58. {
  59. quers[i] = sc.nextInt();
  60. results.put(quers[i], 0);
  61. }
  62.  
  63. BufferedWriter writer = new BufferedWriter(new FileWriter("output.txt"));
  64.  
  65. int count = 0;
  66. for (int i = 0; i < m; i++)
  67. {
  68. int currentQuery = quers[i];
  69.  
  70. if (results.get(currentQuery)==0) {
  71. results.put(currentQuery,(binarySearch(arr, 0, n - 1, currentQuery) + 1));
  72. count++;
  73. }
  74.  
  75. writer.write(results.get(currentQuery)+"\n");
  76. }
  77.  
  78. //writer.write((int)count+"\n");
  79. writer.close();
  80. }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement