Divide-N-Conquer

Problem We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess. You call a pre-defined API int guess(int num), which returns three possible results: -1: Your guess is higher than the number I picked (i.e. num > pick). 1: Your guess is lower than the number I picked (i.e. num < pick). 0: your guess is equal to the number I picked (i.e. num == pick). Return the number that I picked. ...

Problem Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. You must write an algorithm with O(log n) runtime complexity. Examples Example 1: Input: nums = [1,3,5,6], target = 5 Output: 2 ...

Problem Given a sorted array of distinct integers, write a function to find the magic index or fixed point in the array, else return -1. Definition Magic index or a Fixed point in an array is an index i in the array A such that A[i] = i. Examples Example 1: Input: nums = [-6, 0, 2, 40] Output: 2 ...

Problem There are two sorted arrays nums1 and nums2 of size n. Find the median of the two sorted arrays. You may assume nums1 and nums2 cannot be both empty. OR There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Median Definition Median Definition ...

Problem Given a sorted array and an element, find last occurrence of element in array. Examples Example 1: Input: a = [1, 4, 4, 10, 10, 15, 20], target = 10 Output: 4 This problem is similar to Find first position of target element in sorted array. Solution A brute force solution involves scanning the entire array and comparing each A[index] with the key. If A[index] is equal to the key and the next element is different, return the index. The worst-case time complexity of this method is ( O(N) ). Can we improve this? And the answer is yes, using Binary Search on Sorted Array. ...