Leetcode: Hard level problems made easy.

Let’s talk about a simple but powerful tool — binary search. Some people may underestimate it, and think it’s a primitive tool, but the truth is, it is used in a significant number of applications. Let’s have a look at a few real-life examples:

1. Simple old-school dictionary search (not a data structure).

For a 1000-page dictionary, we only need about 10 checks to find a specific word. Some of you, who are old enough, could’ve used it. The algorithm looks like this:

• Open the dictionary somewhere in the middle.
• Compare the first letter of the first word on a page to the first letter of the word we are searching for.
• If the first letter of the word we’re searching for is below the first letter of the page in the alphabet, then all the pages above are eliminated and vice versa.
• Repeat until the word found.

2. Find the square root of a number.

3. Ternary search.

4. 3D game development.

A binary search is used to identify which subdivision of space to display according to a 3D position or camera.

Finally, problem-solving.

Let’s start with a ‘median of two sorted arrays’ problem. The overall run time complexity should be O(log (m+n)).

First of all, we need to define the median.

The median is the value separating the higher half from the lower half of a data sample.

If the count of elements in the set of data is odd, then the median of a sorted array would be the middle element:

A=[1, 2, 3, 4, 5, 6, 7, 8, 9];

median(A)=5;

If the count of elements is even, the median would be an average of two central elements:

A=[1, 2, 3, 4];

median(A)=(2+3)/2=2.5;

So, here we can see the main feature of a median:

(1) Median divides a set into two equal length subsets, where one subset is always higher than the other.

We can solve it an easy way by merging these two arrays, which would result in an O(n+m) complexity. However, this doesn’t fit the requirements of O(log(m+n)).

We have sorted arrays and the O(log(m+n)) complexity, and it should give us a hint on the solution — binary search. Let’s try to adapt the binary search algorithm here.

We have an input of two arrays nums1 and nums2. nums1 = [1, 3, 5]

nums2 = [2, 4, 6], n=len(nums1), m=len(nums2);

We need to find i for nums1 and j for nums2 that it splits arrays into two parts: i -> choose using binary search algorithm

j = (n+m+1) / 2-i;

len(leftNums1)+len(leftNums2)==len(rightNums1)+len(rightNums2);

max(leftNums1)<min(rightNums2);

max(leftNums2)<min(rightNums1);

After we found such indexes:

if ((n+m) mod 2==0)

median=max(nums1[i-1], nums[j -1])+min(nums1[i], nums2[j])

else median=max(nums1[i-1], nums[j-1])

Also we need to make sure n<=m or j can be negative.

Let’s write the code:

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
   if (nums1.Length > nums2.Length)
   {
       int[] temp = nums1;
       nums1 = nums2;
       nums2 = temp;
   }
   int n = nums1.Length, m = nums2.Length;
   int middle = (n + m + 1) / 2;
   int low = 0, high = nums1.Length;
   while (low <= high)
   {
       int i = (low + high) / 2;
       int j = middle - i;
       if (i > low && nums1[i - 1] > nums2[j])
       {
           high = i - 1;
       } else if (i < high && nums2[j - 1] > nums1[i])
       {
           low = i + 1;
       }
       else
       {
           int maxLeft;
           if (i == 0) maxLeft = nums2[j - 1];
           else if (j == 0) maxLeft = nums1[i - 1];
           else maxLeft = Math.Max(nums1[i - 1], nums2[j - 1]);
           if ((m + n) % 2 != 0) return maxLeft;
           int minRight;
           if (i == n) minRight = nums2[j];
           else if (j == m) minRight = nums1[i];
           else minRight = Math.Min(nums1[i], nums2[j]);
           return (minRight + maxLeft) / 2.0;
       }
   }
   return 0;
}

The second problem is, “Find Minimum in Rotated Sorted Array II.” As we see in the description, the array may contain duplicates.

Here is an example of an array rotation:

[0, 2, 5, 6, 7, 7, 8, 10, 11] -> [7, 8, 10, 11, 0, 2, 5, 6, 7];

[0, 10, 10, 10] -> [10, 0, 10, 10];

First of all, we need to simplify the problem. Try to find the solution for an array without duplicates, and then adapt the solution for an array with duplicates.

A = [4, 5, 6, 7, 0, 1, 2];

As we can see, the smallest element would always be the first element that is smaller than the previous one. Here, i = 4. A[i] is the smallest element in the array and A[i] <= A[i-1].

Now, we need to apply a binary search algorithm to find that element:

1. start = 0, end = A.length.
2. Get a middle element middle = (start+end) / 2.
3. If middle+1 < end and A[middle] > A[middle+1] then we found the solution. Return A[middle+1].
4. If middle-1 > start and A[middle] < A[middle-1] than we found the solution. Return A[middle].
5. If we haven’t found the solution, we need to decide where to search.
6. If A[middle] > A[end] than start = middle+1. Go to step 2.
7. If A[start] > A[middle] then end = middle-1. Go to step 2.
8. Else return A[start].

Now, as long as we have the solution for a non-repeated array, it can be adapted to an array with repeating elements.

A = [10, 1, 10, 10];

The solution would be pretty much the same, but with a few additional checks:

1. start = 0, end = A.length.
2. Check whether start == end or start == end — 1 then return min(A[start], A[end]).
3. Get a middle element middle = (start+end) / 2.
4. If middle+1 < end and A[middle] > A[middle+1] then we found the solution. Return
5. A[middle+1].
6. If middle-1 > start and A[middle] < A[middle-1] than we found the solution. Return A[middle].
7. If we haven’t found the solution, we need to decide where to search.
8. If A[middle] > A[end] than start = middle+1. Go to step 2.
9. If A[start] > A[middle] then end = middle-1. Go to step 2.
10. If A[start] == A[middle] and A[middle] == A[end] then we need to search on two halfs recursively [start, … middle] and [middle+1, …end] and return a minimum of these two results.
11. Else return A[start].

And code:

public int FindMin(int[] nums) 
{
    return FindMinRecursive(nums, 0, nums.Length - 1);
}

public int FindMinRecursive(int[] nums, int start, int end) 
{
    if (start == end ||start == end - 1) 
    {
        return Math.Min(nums[start], nums[end]);
    }
    int middle = (start + end) / 2;
    if (middle - 1 > 0 && nums[middle] < nums[middle - 1]) {
        return nums[middle];
    }
    if (middle + 1< nums.Length && nums[middle + 1] < nums[middle])
    {
        return nums[middle + 1];
    }
    if (nums[end] < nums[middle])
    {
        return FindMinRecursive(nums, middle+1, end);
    }
    if (nums[middle] < nums[start]) {
        return FindMinRecursive(nums, start, middle);
    }
    if (nums[middle] == nums[end] && nums[end] == nums[start])
    {
        return Math.Min(FindMinRecursive(nums, middle + 1, end), 
            FindMinRecursive(nums, start, middle));
    }
 
    return nums[start];
}

PS. If you are using C#, you should use type identifiers instead of ‘var’ for performance reasons.

I hope this gave you an idea of what a binary search can be used for.