Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- class MyCode {
- /*
- * Closest Value
- *
- * Given a sorted bit array of integers, and a target value, find the number in the array that is closest to the target.*
- *
- * **Parameters**
- * Input: arr {Array of Integers}
- * Input: target {Integer}
- * Output: {Integer}
- *
- * **Constraints**
- * If there are two numbers tied for the closest value, return the lowest value.
- *
- * Time: O(logN)
- * Space: O(1)
- *
- * **Examples**
- * `[1, 2, 3, 5, 5, 7, 9, 10, 11], 6 --> 5`
- * `[1, 2, 3], 8 --> 3`
- * `[1, 10, 22, 59, 67, 72, 100], 70 --> 72`
- */
- public static void main (String[] args) {
- int[] arr2 = {1, 10, 22, 59, 67, 72, 100};// l = 9 init mid = 4
- int target = 70;
- System.out.println(closestValue(arr2, target));
- }
- public static int closestValue(int[] arr, int target) {
- int len = arr.length;
- if(target <= arr[0]){
- return arr[0];
- }
- if(target >= arr[len - 1]){
- return arr[len-1];
- }else{
- int left = 0;
- int right = len-1;
- while(left <= right){
- int mid = (left + right)/2;
- if(arr[mid] == target){
- return target;
- }
- if(target < arr[mid]){
- right = mid - 1;
- }else if(target > arr[mid]){
- left = mid + 1;
- }
- }
- //check for the difference between target and the 2 numbers and return the lesser difference
- return (arr[left] - target) < (target - arr[right]) ? arr[left] : arr[right];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement