DEV Community

Wenqi Jiang
Wenqi Jiang

Posted on

Binary Search Templates

Reference

Request

  1. Sorted Array
  2. Need N(logN)

Templates

1. Standard Templates

class BinarySearch {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

Enter fullscreen mode Exit fullscreen mode

2. Binary Search Left Boundary

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

Enter fullscreen mode Exit fullscreen mode

Practice Fixed-Point

3. Binary Search Right Boundary

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1) + 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }
}

Enter fullscreen mode Exit fullscreen mode

practice Guess-the-Root

Conclusion

type while left update right update mid return
standard left <= right left = mid - 1 right = mid + 1 (left + right) / 2 -1 / mid
left boundary left < right left = mid - 1 right = mid (left + right) / 2 -1 / left
right boundary left < right left = mid right = mid - 1 (left + right) / 2 + 1 -1 / right

Discussion (0)