Day 44 | Binary Search Practice [Leetcode] | C++

Search Insert Position [Easy]

Solution

We have to find the first index where any element was greater than our target. In case an equal match is there, then it is straightforward the answer

Solution Implementation

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1, ans = nums.size();
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(nums[mid] == target)return mid;
            if(nums[mid] > target){
                ans = mid;
                hi = mid-1;
            }
            else lo = mid + 1;
        }
        return lo;
    }
};

Solution Implementation using STL

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(),nums.end(),target)-nums.begin();
    }
};

Sqrt(X) [Easy]

Solution

We discussed about this problem here.

Solution Implementation

class Solution {
public:
    int mySqrt(int x) {
        int ans = 0, lo = 0, hi = (int)1e5;
        while(lo <= hi){
            int mid = lo + hi >> 1;
            if(mid*1LL*mid <= x)ans=mid,lo = mid+1;
            else hi = mid - 1;
        }
        return ans;
    }
};

Two Sum II - Input Array Is Sorted [Medium]

Solution

Since the array is sorted. Run a loop and assume that one of the indexes is I then another number we need is the target - number[i]. This can either lie in the range [0, i-1] or [i+1, number.size() - 1]

Solution Implementation

class Solution {
public:
    int binary_search(int lo, int hi, int target, vector<int> &arr){
        if(hi < lo)return -1;
        int mid = ( lo + hi ) / 2;
        if(arr[mid] == target)return mid;
        if(arr[mid] > target)
            return binary_search(lo, mid-1, target, arr);
        else 
            return binary_search(mid + 1, hi, target, arr);
        return -1;
    }
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for(int i = 0; i < n; i++){
            int other_index = binary_search(0, i-1, target - numbers[i], numbers);
            if(other_index != -1){
                return {other_index + 1, i + 1};
            }
            other_index = binary_search(i+1, n - 1, target - numbers[i], numbers);
            if(other_index != -1){
                return {i + 1, other_index + 1};
            }
        }
        return {};
    }
};

Minimum Size Subarray Sum [Medium]

Solution

We can run a binary search and check if a window of length X exists with sum >= target or not by the sliding-window.

As described in method any_window_of_length_with_sum_greater_than_x below.

Solution Implementation

class Solution {
public:
    
    bool any_window_of_length_with_sum_greater_than_x(int x, int length, vector<int>& arr){
        int sum = accumulate(arr.begin(), arr.begin() + length, 0);
        if(sum >= x)return true;
        for(int i = length; i < arr.size(); i++){
            sum -= arr[i-length];
            sum += arr[i];
            if(sum >= x)return true;
        }
        return false;
    }
    
    int minSubArrayLen(int target, vector<int>& nums) {
        int lo = 0, hi = nums.size(), ans = 0;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(any_window_of_length_with_sum_greater_than_x(target, mid, nums)){
                ans = mid;
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }
        return ans;
    }
};

Please like and share my posts if they are helpful.