Advertisement
gelita

Find Closest Value in array of integers

Feb 10th, 2020
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.66 KB | None | 0 0
  1.  
  2.   import java.io.*;
  3.   import java.util.*;
  4.  
  5.   class MyCode {
  6.    /*
  7.  * Closest Value
  8.  *
  9.  * Given a sorted bit array of integers, and a target value, find the number in the array that is closest to the target.*
  10.  *
  11.  * **Parameters**
  12.  * Input: arr {Array of Integers}
  13.  * Input: target {Integer}
  14.  * Output: {Integer}
  15.  *
  16.  * **Constraints**
  17.  * If there are two numbers tied for the closest value, return the lowest value.
  18.  *
  19.  * Time: O(logN)
  20.  * Space: O(1)
  21.  *
  22.  * **Examples**
  23.  * `[1, 2, 3, 5, 5, 7, 9, 10, 11], 6 --> 5`
  24.  * `[1, 2, 3], 8 --> 3`
  25.  * `[1, 10, 22, 59, 67, 72, 100], 70 --> 72`
  26.  */
  27.  
  28.      public static void main (String[] args) {
  29.       int[] arr2 = {1, 10, 22, 59, 67, 72, 100};// l = 9 init mid = 4
  30.       int target = 70;
  31.       System.out.println(closestValue(arr2, target));  
  32.     }
  33.      
  34.      
  35.       public static int closestValue(int[] arr, int target) {
  36.         int len = arr.length;
  37.         if(target <= arr[0]){
  38.           return arr[0];
  39.         }
  40.         if(target >= arr[len - 1]){
  41.           return arr[len-1];
  42.         }else{
  43.           int left = 0;
  44.           int right = len-1;
  45.           while(left <= right){
  46.             int mid = (left + right)/2;
  47.             if(arr[mid] == target){
  48.                 return target;
  49.             }
  50.             if(target < arr[mid]){
  51.               right = mid - 1;
  52.             }else if(target > arr[mid]){
  53.               left = mid + 1;
  54.             }
  55.           }
  56.           //check for the difference between target and the 2 numbers and return the lesser difference
  57.           return (arr[left] - target) < (target - arr[right]) ? arr[left] : arr[right];
  58.         }
  59.       }
  60.   }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement