Guest User

Untitled

a guest
Sep 11th, 2019
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class FixedPoint {
  2.  
  3. // 1064: Fixed Point
  4.  
  5. /*
  6. Given an array of n distinct integers sorted in ascending order,
  7. write a function that returns a Fixed Point in the array,
  8. if there is any Fixed Point present in array, else returns -1.
  9.  
  10. Fixed Point in an array is an index i such that arr[i] is equal to i.
  11. Note that integers in array can be negative.
  12. */
  13.  
  14. int binarySearch(int[] arr, int low, int high) {
  15. if (high >= low ){
  16. int mid = (low + high) / 2;
  17.  
  18. if (arr[mid] == mid)
  19. return mid;
  20.  
  21. if (arr[mid] > mid)
  22. return binarySearch(arr, low, mid -1);
  23.  
  24. return binarySearch(arr, mid + 1, high);
  25. }
  26. return -1;
  27. }
  28.  
  29. public static void main(String[] args) {
  30. FixedPoint fx = new FixedPoint();
  31. int[] arr = {-1, 0, 2, 4, 9};
  32. int n = arr.length;
  33.  
  34. int result = fx.binarySearch(arr, 0, n - 1);
  35. System.out.println(result);
  36. }
  37.  
  38. }
RAW Paste Data