Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Binary Search Revision
DSA

Binary Search Revision

Quickly revise binary search fundamentals, boundaries, invariants, and common variations.

1 Classic Binary Search

function binarySearch(nums, target):
    lo = 0, hi = n-1

    while lo <= hi:
        mid = lo + (hi - lo) / 2

        if nums[mid] == target: return mid
        if nums[mid] < target: lo = mid + 1
        else: hi = mid - 1

    return -1
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return -1;
}
def search(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target: return mid
        elif nums[mid] < target: lo = mid + 1
        else: hi = mid - 1

    return -1
int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return -1;
}
function search(nums, target) {
    let lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);

        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return -1;
}

2 Search on Answer

function binarySearchOnAnswer(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo) / 2

        if feasible(mid): hi = mid
        else: lo = mid + 1

    return lo
public int minMax(int[] nums, int k) {
    int lo = 1, hi = 1000000000;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(nums, mid, k)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}
def minMax(nums, k):
    lo, hi = 1, 1000000000

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if canSplit(nums, mid, k): hi = mid
        else: lo = mid + 1

    return lo
int minMax(vector<int>& nums, int k) {
    int lo = 1, hi = 1000000000;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(nums, mid, k)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}
function minMax(nums, k) {
    let lo = 1, hi = 1000000000;

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (canSplit(nums, mid, k)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

3 Binary Search on Rotated Array

function searchRotated(nums, target):
    lo = 0, hi = n-1

    while lo <= hi:
        mid = lo + (hi - lo) / 2

        if nums[mid] == target: return mid

        if nums[lo] <= nums[mid]:
            if target >= nums[lo] && target < nums[mid]:
                hi = mid - 1
            else: lo = mid + 1
        else:
            if target > nums[mid] && target <= nums[hi]:
                lo = mid + 1
            else: hi = mid - 1

    return -1
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {
            if (target >= nums[lo] && target < nums[mid])
                hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[hi])
                lo = mid + 1;
            else hi = mid - 1;
        }
    }

    return -1;
}
def search(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target: return mid

        if nums[lo] <= nums[mid]:
            if target >= nums[lo] and target < nums[mid]:
                hi = mid - 1
            else: lo = mid + 1
        else:
            if target > nums[mid] and target <= nums[hi]:
                lo = mid + 1
            else: hi = mid - 1

    return -1
int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {
            if (target >= nums[lo] && target < nums[mid])
                hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[hi])
                lo = mid + 1;
            else hi = mid - 1;
        }
    }

    return -1;
}
function search(nums, target) {
    let lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);

        if (nums[mid] === target) return mid;

        if (nums[lo] <= nums[mid]) {
            if (target >= nums[lo] && target < nums[mid])
                hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[hi])
                lo = mid + 1;
            else hi = mid - 1;
        }
    }

    return -1;
}

4 Search in Sorted Matrix

function searchMatrix(matrix, target):
    rows = n, cols = m
    lo = 0, hi = n*m - 1

    while lo <= hi:
        mid = lo + (hi - lo) / 2
        midVal = matrix[mid/cols][mid%cols]

        if midVal == target: return true
        if midVal < target: lo = mid + 1
        else: hi = mid - 1

    return false
public boolean searchMatrix(int[][] matrix, int target) {
    int n = matrix.length, m = matrix[0].length;
    int lo = 0, hi = n * m - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = matrix[mid / m][mid % m];

        if (val == target) return true;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return false;
}
def searchMatrix(matrix, target):
    n, m = len(matrix), len(matrix[0])
    lo, hi = 0, n * m - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        val = matrix[mid // m][mid % m]

        if val == target: return True
        elif val < target: lo = mid + 1
        else: hi = mid - 1

    return False
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int n = matrix.size(), m = matrix[0].size();
    int lo = 0, hi = n * m - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = matrix[mid / m][mid % m];

        if (val == target) return true;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return false;
}
function searchMatrix(matrix, target) {
    const n = matrix.length, m = matrix[0].length;
    let lo = 0, hi = n * m - 1;

    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        const val = matrix[Math.floor(mid / m)][mid % m];

        if (val === target) return true;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return false;
}

5 Lower Bound / Upper Bound

function lowerBound(nums, target):
    lo = 0, hi = n

    while lo < hi:
        mid = lo + (hi - lo) / 2
        if nums[mid] >= target: hi = mid
        else: lo = mid + 1

    return lo
public int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}
def lowerBound(nums, target):
    lo, hi = 0, len(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= target: hi = mid
        else: lo = mid + 1

    return lo
int lowerBound(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}
function lowerBound(nums, target) {
    let lo = 0, hi = nums.length;

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

My Private Notes

Notes are auto-saved locally to this device.