Binary Search on Answer

Table of Contents

1. Introduction
2. Conditions for Binary Search on Unsorted Arrays
3. Template for Binary Search on Unsorted Arrays
4. Time Complexity
5. Handling Integer Overflows
6. Conclusion

1. Introduction

Binary search is commonly associated with sorted arrays, but it can also be applicable to unsorted arrays in certain cases. These types of problems are known as "binary search on answer" problems. In this article, we will explore how binary search can be used on unsorted arrays and provide a template for solving such problems.

2. Conditions for Binary Search on Unsorted Arrays

When considering whether binary search is applicable to an unsorted array, we typically look for the following conditions:

• The constraint on the array size is within a reasonable range, often less than or equal to 10^5.
• The problem requires finding the minimum of maximums, maximum of minimums, or some other form of minimum or maximum value.
• The problem exhibits a monotonic nature, where the target value can be determined based on a specific condition.

3. Template for Binary Search on Unsorted Arrays

Here's a template you can use to implement binary search on unsorted arrays:

bool isValid(vector<int>& nums, int mid, int k) {
    // Check if a certain condition 'k' holds true for the given 'mid'
    // Return true or false accordingly
}

int binarySearch(vector<int>& nums, int k) {
    int low = INT_MIN; // Set the lower bound
    int high = INT_MAX; // Set the upper bound
    int result = -1; // Initialize the result variable

    while (low <= high) {
        int mid = low + (high - low) / 2;    // Calculate the mid value

        if (isValid(nums, mid, k)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

4. Time Complexity

The time complexity of binary search on unsorted arrays is typically N * log(Range of Binary Search), where N is the size of the array and the Range of Binary Search is the difference between the maximum and minimum possible answers.

5. Handling Integer Overflows

It's important to be cautious about integer overflows when calculating the mid value. To avoid this, alternative methods can be used, such as low + (high - low) / 2 or (low + high) >> 1, which are less prone to overflow issues.

6. Conclusion

By following this approach, we can effectively apply binary search to unsorted arrays and solve related problems. You can practice some more problems using this format to gain confidence in solving this type of problem. Hopefully, I will write another article with more example problems in the future.

Problem 1: Find the smallest element in an unsorted array that is larger than a given target value.

Explanation: In this problem, we need to find the smallest element in the array that is greater than the target value. We can use the binary search template to solve this. The isValid function will check if a certain element is larger than the target, and the binarySearch function will perform the binary search to find the smallest element that satisfies the condition.

Problem 2: Find the largest element in an unsorted array that is smaller than a given target value.

Explanation: This problem is similar to the previous one, but we need to find the largest element smaller than the target value. We can again use the binary search template, but this time the isValid function will check if a certain element is smaller than the target, and the binarySearch function will perform the binary search to find the largest element that satisfies the condition.

Problem 3: Determine if a certain number of elements in an unsorted array are greater than or equal to a given threshold.

Explanation: In this problem, we are given a threshold value and we need to determine if a certain number of elements in the array are greater than or equal to that threshold. We can use the binary search template by modifying the isValid function to count the number of elements greater than or equal to the threshold and check if it satisfies the given condition.

Problem 4: Find the maximum possible value that satisfies a given condition in an unsorted array.

Explanation: This problem requires finding the maximum value in the array that satisfies a given condition. We can utilize the binary search template by modifying the isValid function to check if a certain value satisfies the given condition and finding the maximum value that satisfies it using binary search.

These are just a few examples to demonstrate how the binary search template can be used to solve different types of problems on unsorted arrays. You can apply the template to various other problem statements by adapting the isValid function to match the specific condition you need to check.