Coding

8 flashcards · Programming Languages · by Temi Dipo-ayeni

1. Write a binary search to find the the closest number to a target not in a list (not exceeding it)

   [2,4,6] looking for 5. Return 4 We keep updating the value right before the number becomes too large. This is the number we get while the found number is < target, going right. The found number is always greater than the target, we will never hit that block where the number we find is less than i.e. all numbers are larger out target. In that case, we need to return the first element E.g. [2,4,6] looking for 5. return 0 int left = 0; int right = arr.length - 1; closestTimestamp= -1; while(left <…

2. Write a binary search to find the the closest number just exceeding a number not in a list

   As soon as it is larger than target [2,4,6,8] , 3 int left = 0; int right = arr.length - 1; closestTimestamp= -1; while(left <= right) { int mid = left + (right - left)/2; if(arr[mid] > target) { closestTimestamp= arr[mid] right = mid - 1; }else if(arr[mid] < target) { left = mid + 1; } if(closestTimestamp == -1) { //all too small closestTimestamp = arr[length - 1] } }

3. In binary search if the number found it too large which direction to you go. What is the pointer you move

   left right = mid - 1

4. In binary search if the number found it too small which direction to you go. What is the pointer you move

   right left = mid + 1

5. In binary search, when searching for a number that is not in the array, but you want to get the one closest to it without exceeding it, which element do you want? What do you do to get that element?

   [2,4,6] , 5 -> 4 BIGGEST SMALLer number keep updating small number as you get closer You want the element that is less than, so keep recording that until it is exceeded. So you put a variable in the condition where the found number is less than the target and you are going right. //too small, go right if(arr[mid] < target) { left = mid + 1 closestNum = arr[mid] }

6. In binary search, when searching for a number that is not in the array, but you want to get the one closest to it without exceeding it, which element do you want? What do you do if the element is not there.

   [2,4,6], 0 -> 2 All numbers larger than target initially set closestNum = -1 as invalid then closestNum = arr[0]

7. In binary search, when searching for a number that is not in the array, but you want to get the one closest to it just exceeding it, which element do you want? What do you do to get that element?

   The smallest big number [2,4,6, 8] , 5 -> 6 ^ Last too big number before getting it right if(arr[mid] > target) { right = mid - 1; closestNum = mid }

8. In binary search, when searching for a number that is not in the array, but you want to get the one closest to it just exceeding it, which element do you want? What do you do if the element is not there.

   [2,4,6,8], 10 All nums are too small so never enter too big initially set closestNum = -1 as invalid then closestNum = arr[len - 1]