关于二分查找(Binary Search)及其变种形式的总结

二分查找是基本算法,但是据统计只有10%的程序员可以写出没有bug的代码。出错的原因主要集中在对边界值得选择和判定条件上,一不小心就可能导致超出边界或者死循环的情况。这里作如下总结:

标准版二分查找:
在有序(非降序)数组中查找一个target值,数组中元素没有重复,找到target则返回该元素对应的index,找不到则返回-1。

注意1:如果是start < end,那么当target等于num[num.length-1]时,会找不到该值。 注意2:因为num[mid] > target, 所以如果有num[index] == target, index一定小于mid,能不能写成end = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成end = mid,当循环到start = 0, end = 0时(即num[start] = 1, num[end] = 1时),mid将永远等于0,此时end也将永远等于0,陷入死循环。也就是说寻找target = -2时,程序将死循环。

注意3:因为num[mid] < target, 所以如果有num[index] == target, index一定大于mid,能不能写成start = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。也就是说寻找target = 9时,程序将死循环。

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //注意2
        }
        else{
            start = mid + 1; //注意3
        }
    }
    return -1;
}

二分查找变形一:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最小值,找不到则返回-1。

注意1:为了对左右相邻的两个数进行对比,循环结束的时候,start和end应该相隔1。

注意2:a). 当num[mid] == target时,此时并不能直接返回mid,因为有可能num[mid-1]或者num[mid-2]…也等于target,所以此时应该将end  = mid,然后继续循环。b). 当num[mid] > target时,如果有num[index] == target,那么index一定小于mid,本来按此道理应该令end = mid – 1,但是为什么此处可以end = mid呢?回头去看上一题(标准版)的注意2,只有当start = end时,才会出现死循环的情况。这里因为while循环的限制条件使得start和end永远不可能相等,所以end = mid也是正确的。由此,我们可将a) 和 b) 两种情况合并。

注意3:这里与上题一致,不用有变化。但是在这里写成start = mid也是成立的,为啥呢?回头看上题的注意3,同样的例子num = {1, 2, 5, 7, 9}; 在上题中,如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。但在此题中由于while中的限制条件的变化,避免了这种死循环的发生。

注意4:此处为什么要分别检验num[start]和num[end]是否等于target呢?因为这两个值都有可能等于target,取决于中间二分时start和end的更新过程。这里随便用几个简单的例子即可验证。如果循环结束时num[start] == num[end] == target,根据题意应该返回start,所以我们先验证start。如果两个值都不是target,则target不存在,返回-1。

public int binarySearchMinimumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意2
            end = mid;
        }
        else{
            start = mid + 1; //注意3
        }
    }
    if(num[start] == target) //注意4
        return start;
    else if(num[end] == target)
        return end;
    else
        return -1;
}

二分查找变形二:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最大值,找不到则返回-1。

道理与上一题相同,只要在注意2和注意3处与上题反过来就行了,原理不重复了,拿不准的时候可以用几个简单的test case测试一下。

public int binarySearchMaximumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){ //注意2
            start = mid;
        }
        else{
            end = mid - 1; //注意3
        }
    }
    if(num[end] == target)
        return end;
    else if(num[start] == target) //注意4
        return start;
    else
        return -1;
}

二分查找变形三:
在有序(非降序)数组中查找一个可能的”最大”index,使得num[index] < target,数组中元素可能有重复,找不到则返回-1。

注意1:我们可以对此步分开考虑,当num[mid] == target时,因为我们要求num[index] < target,所以index必须在mid左边。当num[mid] > target时,target肯定在num[mid]的左边,所以index肯定也要在mid的左边。那么再多想一步,假如num[mid] >= target时,我们进行了end = mid的操作,会产生什么后果呢?经我的有限测试,好像并没有什么问题,因为while中的限制条件导致了每当start + 1 == end的时候,循环就结束了,所以标准版二分查找中出现的死循环的情况并不存在。

注意2:当num[mid] < target时,为什么此处用start = mid而不是start = mid + 1?因为有可能num[mid+1] == target,此时如果start = mid + 1, 则num[start] == target,明显错过了正解。

public int binarySearchClosestFromLeft(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意1
            end = mid - 1;
        }
        else{ //注意2
            start = mid;
        }
    }
    if(num[end] < target){
        return end;
    }
    else if(num[start] < target){
        return start;
    }
    else{
        return -1;
    }
}

二分查找变形四:
在有序(非降序)数组中查找一个可能的”最小”index,使得num[index] > target,数组中元素可能有重复,找不到则返回-1。
道理与上题完全相同,稍作调整即可。

注意1:此处同上题注意1原理相同,写成start = mid也应该没有问题。

public int binarySearchClosestFromRight(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){
            start = mid + 1; //注意1
        }
        else{
            end = mid;
        }
    }
    if(num[start] > target){
        return start;
    }
    else if(num[end] > target){
        return end;
    }
    else{
        return -1;
    }
}

综上所述,总结规律:
1. 当数组中没有重复元素时:while循环判定条件是(start <= end),每次start更新为mid + 1,end更新为mid – 1。
2. 当数组中含有重复元素时或者要找的值是target的相邻数时,判定条件是(start + 1 < end),当num[mid] == target时,并不返回mid,而是根据情况跟新start或者end。每次start更新为mid,end也更新为mid即可。

Advertisements

Fast Power, LintCode

Calculate the an % b where a, b and n are all 32bit integers.

Example
For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge
O(logn)

数学问题,要求O(log n)的时间复杂度,也就是每次去掉一半的计算量,先要找到对应的数学公式:
(a * b) % p = (a % p * b % p) % p

所以(a^n)%b = (a^n/2 * a^n/2 * a) % b = ((a^n/2 * a^n/2)%b * a%b) % b
注意int和long的转化,防止溢出。

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        long ret = getPower(a, b, n);
        return (int)ret;
    }
    public long getPower(int a, int b, int n){
        if(a == 0) return 0;
        if(n == 0) return 1 % b;
        if(n == 1) return a % b;
        
        long ret = getPower(a, b, n/2);
        ret *= ret;
        ret %= b;
        if(n % 2 == 1){
            ret = ret * (a % b);
        }
        return ret % b;
    }
};

Binary Search Duplicated Values

Binary search is easy, but what if there are duplicated elements in the sorted array and you need to find the first index of the target value?

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        while(left < right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                result = mid;
                right = mid;
            }
            else if(nums[mid] > target){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return result;
    }
}

Backpack II, LintCode

Given n items with size A[i] and value V[i], and a backpack with size m. What’s the maximum value can you put into the backpack?
Note
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

背包问题是一个经典的算法问题,可以用动态规划的方法来解,网上找到的最好的解释是:
http://love-oriented.com/pack/P01.html
基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度
以上方法的时间和空间复杂度均为O(VN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到O。

先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下:

for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。

事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。

过程ZeroOnePack,表示处理一件01背包中的物品,两个参数cost、weight分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。

有了这个过程以后,01背包问题的伪代码就可以这样写:

for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。

一个常数优化
前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进。

由于只需要最后f[v]的值,倒推前一个物品,其实只要知道f[v-w[n]]即可。以此类推,对以第j个背包,其实只需要知道到f[v-sum{w[j..n]}]即可,即代码中的

for i=1..N
for v=V..0
可以改成

for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。

小结
01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[][] dp = new int[A.length+1][m+1];
        for(int i = 0; i <= A.length; i++){
            for(int j = 0; j <= m; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                }
                else if(A[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }
            }
        }
        return dp[A.length][m];
    }
}

A + B Problem, LintCode 解题笔记

For given numbers a and b in function aplusb, return the sum of them.

Note
You don’t need to parse the input and output. Just calculate and return.

Example
If a=1 and b=2 return 3

Challenge
Can you do it with out + operation?

Clarification
Are a and b both 32-bit integers?
– Yes.

位运算实现整数加法本质就是用二进制进行运算。
其主要用了两个基本表达式:
x^y //执行加法,不考虑进位。
(x&y)<<1 //进位操作
令x=x^y ;y=(x&y)<<1 进行迭代,每迭代一次进位操作右面就多一位0,最多需要“加数二进制位长度”次迭代就没有进位了,此时x^y的值就是结果。

我们来做个3位数的加法:
101+011=1000 //正常加法
位运算加法:
(1) 101 ^ 011 = 110
(101 & 011)<<1 = 010
(2) 110 ^ 010 = 100
(110 & 010)<<1 = 100
(3) 100 ^ 100 = 000
(100 & 100)<<1 = 1000
此时进行相加操作就没有进位了,即000 ^ 1000=1000即是最后结果。

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        while(b != 0){
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
}

Intersection of Two Linked Lists, Leetcode 解题笔记

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2 → c1 → c2 → c3

B: b1 → b2 → b3 → c1 → c2 → c3
begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

一开始想的是直接同时遍历A和B,A走一步,B走一步,后来发现这样其实等于是两个循环套在一起的意思,时间复杂度变成了O(m*n)。
一个巧妙的方法是先找到list A和list B的长度差,然后让长的那个list先把长出来的那一段走完,此时两个list是一样长的,然后同时向后走直到重合。这样时间复杂度是O(m+n),并且只需要常量的空间。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int numA = 0;
        int numB = 0;
        ListNode cur = headA;
        ListNode cur2 = null;
        while(cur != null){
            cur = cur.next;
            numA++;
        }
        cur = headB;
        while(cur != null){
            cur = cur.next;
            numB++;
        }
        int diff = Math.abs(numA - numB);
        if(numA > numB){
            cur = headA;
            cur2 = headB;
        }
        else{
            cur = headB;
            cur2 = headA;
        }
        for(int i = 0; i < diff; i++){
            cur = cur.next;
        }
        while(cur != null){
            if(cur == cur2) return cur;
            cur = cur.next;
            cur2 = cur2.next;
        }
        return null;
    }
}

Min Stack, Leetcode 解题笔记

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.

这题很简单,维护一个list就可以了,定义一个新的类StackNode,存当前的值和当前的最小值。

class MinStack {
    StackNode stackHead = null;
    
    public void push(int x) {
        StackNode element = new StackNode(x);
        if(stackHead != null){
            element.next = stackHead;
            element.min = Math.min(x, stackHead.min);
            stackHead = element;
        }
        else{
            element.next = null;
            element.min = x;
            stackHead = element;
        }
        
    }

    public void pop() {
        if(stackHead != null)
            stackHead = stackHead.next;
    }

    public int top() {
        if(stackHead != null)
            return stackHead.val;
        else
            return 0;
    }

    public int getMin() {
        if(stackHead != null)
            return stackHead.min;
        else
            return 0;
    }
}
class StackNode {
    StackNode next;
    int val;
    int min;
    StackNode(int val) {
        next = null;
        this.val = val;
        min = 0;
    }
}