二分法题型一

二分位置之 OOXX，一般会给你一个数组，让你找数组中第一个/最后一个满足某个条件的位置：OOOOOOO…OOXX….XXXXXX。

Leetcode - 278 First Bad Version
Lintcode - 159 Find Minimum in Rotated Sorted Array
Leetcode - 74 Search a 2D Matrix
Lintcode - 61 Search for a Range

模板

public int findPosition(int[] nums, int target) {
    // write your code here
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0;
    int right = nums.length - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid;
        }
    }

    if (nums[left] == target)
        return left;
    if (nums[right] == target)
        return right;

    return -1;
}

二分法题型二

第二境界二分位置之 Half half，并无法找到一个条件，形成 OOXX 的模型，但可以根据判断，保留下有解的那一半或者去掉无解的一半

Lintcode - 75 Find Peak Element
Lintcode - 585 Maximum Number in Mountain Sequence

二分答案 Binary Search on Result

往往没有给你一个数组让你二分而且题目压根看不出来是个二分法可以做的题

同样是找到满足某个条件的最大或者最小值

FEATURED TAGS

algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper

【Algorithm】算法思想 - 二分法（Dichotomy）

二分法题型一

模板

二分法题型二

FEATURED TAGS

FRIENDS

TOC