九章二分

    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        // 要点1: start + 1 < end
        while (start + 1 < end) {
        // 要点2：start + (end - start) / 2
            int mid = start + (end - start) / 2;
            // 要点3：=, <, > 分开讨论，mid 不+1也不-1
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        // 要点4: 循环结束后，单独处理start和end
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }

拓扑排序 这是 LintCode 上的题目：Topological Sorting

拓扑排序的算法是典型的宽度优先搜索算法，其大致流程如下：

1. 统计所有点的入度，并初始化拓扑序列为空。
2. 将所有入度为 0 的点，也就是那些没有任何 依赖 的点，放到宽度优先搜索的队列中
3. 将队列中的点一个一个的释放出来，放到拓扑序列中，每次释放出某个点 A 的时候，就访问 A 的相邻点（所有A指向的点），并把这些点的入度减去 1。
4. 如果发现某个点的入度被减去 1 之后变成了 0，则放入队列中。
5. 直到队列为空时，算法结束，

深度优先搜索也可以做拓扑排序，不过因为不容易理解，也并不推荐作为拓扑排序的主流算法。

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // map 用来存储所有节点的入度，这里主要统计各个点的入度
        HashMap<DirectedGraphNode, Integer> map = new HashMap();
        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                if (map.containsKey(neighbor)) {
                    map.put(neighbor, map.get(neighbor) + 1);
                } else {
                    map.put(neighbor, 1); 
                }
            }
        }

        // 初始化拓扑序列为空
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();

        // 把所有入度为0的点，放到BFS专用的队列中
        Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>();
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node)) {
                q.offer(node);
                result.add(node);
            }
        }

        // 每次从队列中拿出一个点放到拓扑序列里，并将该点指向的所有点的入度减1
        while (!q.isEmpty()) {
            DirectedGraphNode node = q.poll();
            for (DirectedGraphNode n : node.neighbors) {
                map.put(n, map.get(n) - 1);
                // 减去1之后入度变为0的点，也放入队列
                if (map.get(n) == 0) {
                    result.add(n);
                    q.offer(n);
                }
            }
        }

        return result;
    }

无需分层遍历的宽度优先搜索

    // T 指代任何你希望存储的类型
    Queue<T> queue = new LinkedList<>();
    Set<T> set = new HashSet<>();

    set.add(start);
    queue.offer(start);
    while (!queue.isEmpty()) {
        T head = queue.poll();
        for (T neighbor : head.neighbors) {
            if (!set.contains(neighbor)) {
                set.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }

需要分层遍历的宽度搜先搜索

    // T 指代任何你希望存储的类型
    Queue<T> queue = new LinkedList<>();
    Set<T> set = new HashSet<>();

    set.add(start);
    queue.offer(start);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            T head = queue.poll();
            for (T neighbor : head.neighbors) {
                if (!set.contains(neighbor)) {
                    set.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

使用两个队列的BFS实现

我们可以将当前层的所有节点存在第一个队列中，然后拓展（Extend）出的下一层节点存在另外一个队列中。来回迭代，逐层展开。

    // T 表示任意你想存储的类型
    Queue<T> queue1 = new LinkedList<>();
    Queue<T> queue2 = new LinkedList<>();
    queue1.offer(startNode);
    int currentLevel = 0;

    while (!queue1.isEmpty()) {
       int size = queue1.size();
        for (int i = 0; i < size; i++) {
            T head = queue1.poll();
            for (all neighbors of head) {
                queue2.offer(neighbor);
            }
        }
        Queue<T> temp = queue1;
        queue1 = queue2;
        queue2 = temp;

        queue2.clear();
        currentLevel++;
    }

使用 Dummy Node 进行 BFS

什么是 Dummy Node

Dummy Node，翻译为哨兵节点。Dummy Node 一般本身不存储任何实际有意义的值，通常用作"占位"，或者链表的“虚拟头”。
如很多的链表问题中，我们会在原来的头head的前面新增一个节点，这个节点没有任何值，但是 next 指向 head。这样就会方便对 head 进行删除或者在前面插入等操作。

head->node->node->node ...
=>
dummy->head->node->node->node...

Dummy Node 在 BFS 中如何使用

在 BFS 中，我们主要用 dummy node 来做占位符。即，在队列中每一层节点的结尾，都放一个null（or None in Python，nil in Ruby），来表示这一层的遍历结束了。这里 dummy node 就是一个 null。

    // T 可以是任何你想存储的节点的类型
    Queue<T> queue = new LinkedList<>();
    queue.offer(startNode);
    queue.offer(null);
    currentLevel = 0;
    // 因为有 dummy node 的存在，不能再用 isEmpty 了来判断是否还有没有拓展的节点了
    while (queue.size() > 1) {
        T head = queue.poll();
        if (head == null) {
            currentLevel++;
            queue.offer(null);
            continue;
        }
        for (all neighbors of head) {
            queue.offer(neighbor);
        }
    }