SHARE
TWEET

Untitled

a guest Sep 11th, 2019 80 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top