跳表：链表上的二分查找

public boolean search(int target) {
    Node cur = head;
    for (int level = maxLevel - 1; level >= 0; level--) {
        while (cur.next[level] != null && cur.next[level].val < target) {
            cur = cur.next[level];
        }
    }
    cur = cur.next[0];   // 底层下一个
    return cur != null && cur.val == target;
}

public void insert(int val) {
    Node[] update = new Node[maxLevel];
    Node cur = head;
    for (int level = maxLevel - 1; level >= 0; level--) {
        while (cur.next[level] != null && cur.next[level].val < val) {
            cur = cur.next[level];
        }
        update[level] = cur;
    }

    int newLevel = randomLevel();
    Node newNode = new Node(val, newLevel);
    for (int i = 0; i < newLevel; i++) {
        newNode.next[i] = update[i].next[i];
        update[i].next[i] = newNode;
    }
}

private int randomLevel() {
    int level = 1;
    while (Math.random() < 0.5 && level < maxLevel) {
        level++;
    }
    return level;
}

public boolean delete(int val) {
    Node[] update = new Node[maxLevel];
    Node cur = head;
    for (int level = maxLevel - 1; level >= 0; level--) {
        while (cur.next[level] != null && cur.next[level].val < val) {
            cur = cur.next[level];
        }
        update[level] = cur;
    }

    cur = cur.next[0];
    if (cur == null || cur.val != val) return false;

    for (int i = 0; i < cur.next.length; i++) {
        update[i].next[i] = cur.next[i];
    }
    return true;
}