• SDE Sheet - 180 FAANG Problems (Striver)
• Kunal Kushwaha - Java + DSA + Interview Course
  • Binary Search Algorithm - Theory + Code
  • Binary Search Interview Questions - Google, Facebook, Amazon
  • Binary Search in 2D Arrays

Condition: Array must be sorted

• Find the middle element (Type 1)
  • ( mid = ( start + end ) / 2 )
• Optimization for finding middle element (Type 2)
  • mid = start + ( (end - start) / 2 )
  • Problem before: Integer Overflow!!! - might be possible that (start + end) exceeds the range of int in Java
• If target > mid => search in the right
• Else => search in left
• If middle element == target element => return (answer)

package com.aswin;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
        int target = 3;
        int ans = binarySearch(arr, target);
        System.out.println(ans);
    }

    // return the index
    // return -1 if it does not exist
    static int binarySearch(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        while(start <= end) {
            // find the middle element
            // int mid = (start + end) / 2;
            // Problem: might be possible that (start + end) exceeds the range of int in Java

            int mid = start + ( (end - start) / 2 );

            if(target < arr[mid]) {
                end = mid - 1;
            } else if (target > arr[mid]) {
                start = mid + 1;
            } else {
                // ans found
                return mid;
            }
        }

        return -1;
    }

}

• During Binary Search, when we access the array elements (at both ends) in search space, we must avoid Array Index Out Of Bounds Error.
• So, always use the following function

int safeGet(int[] A, int i) {
    if(0 <= i && i < A.length) {
        return A[i];
    } else {
        return Integer.MAX_VALUE;
    }
}

• When the array order is unknown ( ascending order or descending order ?)

• Find the middle element
  • ( mid = ( start + end ) / 2 )
• If target > mid => search in the left
• If target < mid => search in right
• Else middle element == target element (answer)

• Just check the start and end
• Steps :
  • if start < end => Ascending order
  • else => Descending order

• One small change in Binary Search logic: find whether the array is sorted in ascending or descending
  • boolean isAsc = arr[start] < arr[end]

package com.aswin;

public class OrderAgnosticBS {
    public static void main(String[] args) {
        int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
        int target = 3;
        int ans = orderAgnosticBS(arr, target);
        System.out.println(ans);
    }

    // return the index
    // return -1 if it does not exist
    static int orderAgnosticBS(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        // find whether the array is sorted in ascending or descending
        boolean isAsc = arr[start] < arr[end];

        while(start <= end) {
            // find the middle element
            // int mid = (start + end) / 2;
            // Problem: might be possible that (start + end) exceeds the range of int in Java

            int mid = start + ( (end - start) / 2 );

            if(arr[mid] == target) {
                // ans found
                return mid;
            }
            if(isAsc) {
                if(target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            else {
                if(target > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }

        }

        return -1;
    }
}

• Sorted array (If we are given as input)
• When you are required to get one particular answer and you are following a continuous sequence to get the answer:
  • Square Root of a number
• Maximize the minimum answer
• Minimize the maximum answer
• Maximize the answer
• Minimize the answer
• much more ...

• Difficulity: Easy to Hard

• Ceiling of number: Smallest element in array which is greater than or equal to target
• Steps
• 1. Find the closest or equal number to target
• 2. Find all the numbers which are greater than the previous result (Binary Search)
• 3. Return the smallest number from the previous category

• Consider the following example:
• arr = [2, 3, 5, 9, 14, 16, 18], target = 14
• ceiling(arr, target=14) = 14
• ceiling(arr, target=15) = 16
• ceiling(arr, target=4) = 5
• ceiling(arr, target=9) = 9

• If target is found, return the target
• Else return the start
• Because when the condition is violated in the while loop: start = end + 1

•   start  target  end              =>              end  target  start
  

• So the answer is not in this range, and the smallest element which is greater than or equal to target is the start

• Ceiling of number: Greatest element in array which is smaller than or equal to target
• Steps
• 1. Find the closest or equal number to target
• 2. Find all the numbers which are smaller than the previous result (Binary Search)
• 3. Return the greatest number from the previous category

• Consider the following example:
• arr = [2, 3, 5, 9, 14, 16, 18], target = 14
• floor(arr, target=4) = 3
• floor(arr, target=9) = 9
• floor(arr, target=14) = 14
• floor(arr, target=19) = 18

• If target is found, return the target
• Else return the end
• Because when the condition is violated in the while loop: start = end + 1

•   start  target  end              =>              target  end  start
  

• So the answer is not in this range, and the greatest element which is smaller than or equal to target is the end

• Similar to Ceiling of a number
• Change: Ignore mid == target condition
• Change: Return start % arr.length as the result

• Apply Binary Search Twice:
• Find the first occurrence of the target - Change: Update ans and end each time
• Find the last occurrence of the target - Change: Update ans and start each time

• In an infinte array of numbers, the size is unknown.
• Binary search divides the array by two for each iteration following Top - down approach
• For this problem, as we are unaware about the end pointer, we will follow Bottom - up approach
• Bottom-up : Start with a small chunk of array and double up the size of the chunk by two for every iteration
• Apply Binary search for each chunk and keep doubling the chunk until the element is found.

• Mountain Array is also known as Bitonic array.

• In this array, the numbers in first part are sorted in increasing order and the second part in decreasing order.

• Peak element is nothing but the maximum element in the array.

• So, we have two cases where we can compare adjacent elements:

  • Ascending part where we can update the start = mid + 1
  • Descending part where we can update the end = mid

• In the end, start == end and pointing to the largest number because of the 2 checks above

• start and end are always trying to find the max element in the above 2 checks

• Hence, when they are pointing to just one element, that is the max one because that is what the checks say

• More elaboration: at every point of the time for start and end,

• they have the best possible answer till that time and if we are saying that only one item is remaining

• hence because of above line that is the best possible ans

• Similar to Peak Index in Mountain Array, except the target is given
• Here, we can first find the Peak Index
• Then, apply Order Agnostic Binary Search in both parts of the Mountain array:
  • 0 -> peakIndex
  • peakIndex+1 -> arr.length - 1
• And, finally return the answer

• Consider an array = [2, 4, 5, 7, 8, 9, 10, 12]
• After 1st rotation, array = [12, 2, 4, 5, 7, 8, 9, 10]
• After 2nd rotation, array = [10, 12, 2, 4, 5, 7, 8, 9]

• pivot is from where your next numbers are ascending
• pivot is also the largest number
• For example: [3, 4, 5, 6, 7, 0, 1, 2]
  • Here, the is pivot = 7
  • Both parts before & after the pivot is sorted in ascending order
• So, we can follow the following steps:
  • Find pivot
  • Search target in first half => Simple BS (0 -> pivot)
  • If still not found, search target in second half => Simple BS (pivot+1, end)
• Now, the problem is to find the pivot:
  • Consider [3, 4, 5, 6, 7, 0, 1, 2]
  • We can observe that only two elements 7, 0 are descending
  • So, when do we find the answer:
    • Case 1: When mid > mid+1 element, then mid is the pivot
    • Case 2: When mid < mid-1 element, then mid-1 is the pivot
    • Case 3: When start >= mid element, then end = mid - 1
    • Case 4: When start < mid element, then start = mid + 1
    • ( Explanation for case 3 & 4: if mid was pivot it would've returned by case 1 & 2... )
    • ( Hence, proved that bigger number lies behind in case 3 and ahead in case 4, so ignore mid in case 3 and 4 using mid (+ or -) 1 )
• Now, we have to find the target:
  • If target == arr[pivot] return pivot
  • If target >= arr[0], Search target in first half => Simple BS (0 -> pivot)
  • If target < arr[pivot] search target in second half => Simple BS (pivot+1, end)

• The approach for duplicates are same as the previous problem except

  • The while loop should terminate when start>=end
  • The Case 3 & 4 will not work for duplicates

• So, we can skip the duplicates by comparing start, mid and end only if they are not pivot elements

• And then we can start reducing the search space based on the comparision of start, mid, and end

• Similar to previous approaches except
  • We return 0 if array's pivot is -1
  • Else we return the pivot+1 as the answer
• Because the array rotates pivot times, and as we get 0-indexed pivot, we return pivot+1 as the answer.

• Find the minimum (minAns) and maximum no. of splits (maxAns) we can make
• Take the minAns and maxAns as start and end respectively
• Apply binary search such that
  • the mid will be (minAns + maxAns) / 2
  • Traverse the array and calculate the cummulative sum to calculate how many pieces you can divide the array with this mid (max sum)
    • if sum becomes greater than mid, then reset sum to current number, and increment the no. of pieces
    • else continue adding sum
  • Now, apply checks for binary search
    • If no. of pieces are greater than m (given no. of partitions) then update start = end + 1
    • Else update end = mid