２次元配列から重複を検索

問題
In a 2-D matrix, every row is increasingly sorted from left to right, and the last number in each row is not greater than the first number of the next row. A sample matrix follows. Please implement a function to check whether a number is in such a matrix or not. It returns true if it tries to find the number 7 in the sample matrix, but it returns false if it tries to find the number 12.

1   3   5

7   9   11

13  15  17

(Coding Interviews: Questions, Analysis & Solutionsより引用)

ヒント

２次元配列である必要などない．

解

基本的には２次元配列である必要がないため，一次元配列にするか，このまま２次元配列に２分検索をするか．ここでは前者の方法をとっている．

package org.tanuneko;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by morinoko on 5/3/2014.
 */
public class DupeFound {

    static int bsearch( List<Integer> l, int val ) {

        int s = 0;
        int e = l.size() - 1;
        int m = 0;
        while( s <= e ) {
            m = l.get((s + e) / 2);
            if (m == val)
                return (s + e) / 2;
            else if (m < val)
                s = ((s + e) / 2) + 1;
            else
                e = ((s + e) / 2) - 1;
        }
        return -1;
    }


    public static void main( String args[] ) {

     
    List<Integer> l = Arrays.asList( "1 3 5", "7 9 11", "13 15 17" )
            .stream()
            .flatMap(x -> Arrays.stream(x.split(" ")))
            .mapToInt(x -> Integer.parseInt(x))
            .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);

    int m = l.get( l.size() / 2 );

    System.out.println( bsearch( l, 5 ) );
    System.out.println( bsearch( l, 14 ) );
}
}