Nice Problem To Test Binary Search and Recursion.


  • 0
    K

    We all know that Binary search is a classic algorithm running on ordered array.
    It's also a common knowledge at recursion is done by decreasing the search scope/ size of the problem.

    Sometimes, the problem can be tricker to ask you to conduct log(m) search on a matrix, or two arrays. They are normally referred to variances of binary search. These problems are super popular to FAMGA as they test your scalability which indicates deep understanding of classic computational thoughts and algorithms.

    The following code is a clean, Python version derived from https://aaronice.gitbooks.io/lintcode/content/array/median_of_two_sorted_arrays.html.

    class Solution(object):
            
        def findkth(self,nums1,start1,nums2,start2,k):
            if start1 >= len(nums1): return nums2[start2+k-1]
            if start2 >= len(nums2): return nums1[start1+k-1]
            if k==1: return min(nums1[start1],nums2[start2])
    
            mid_a = nums1[start1+k/2-1] if start1+k/2-1<len(nums1) else float('inf')
            mid_b = nums2[start2+k/2-1] if start2+k/2-1<len(nums2) else float('inf')
    
            if mid_a < mid_b: return self.findkth(nums1,start1+k/2,nums2,start2,k-k/2)
            else: return self.findkth(nums1,start1,nums2,start2+k/2,k-k/2)
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            length = len(nums1)+len(nums2)
            if length%2==1:
                return self.findkth(nums1,0,nums2,0,length/2+1)
            else:
                return float(self.findkth(nums1,0,nums2,0,length/2+1)+self.findkth(nums1,0,nums2,0,length/2))/2
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.