/* Copyright (C) 2009  CSE,IIT Bombay  http://www.cse.iitb.ac.in

This file is part of the ConStore open source storage facility for concept-nets.

ConStore is free software and distributed under the 
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License;
you can copy, distribute and transmit the work
with the work attribution in the manner specified by the author or licensor.
You may not use this work for commercial purposes and may not alter, 
transform, or build upon this work.

Please refer the legal code of the license, available at
http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode

ConStore is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  */

package iitb.con.util;

/**
 * Integer Binary search for 2D integer array.
 * The search is performed on the specified column and 
 * the column need to be sorted before the search. 
 * 
 * @author Prathab K
 *
 */
public class Int2DBinarySearch {
    
    /** Binary search of on 2d integer array 
     *  @param a array of sorted values to be searched.
     *  @param key  value to be located
     *  @return  returns index of the first match, or -insertion_position
     */
    public static int locate(int[][] a, int key, int col) {
        int low = 0;
        int high = a.length - 1;
        int mid;
        
        while (low < high) {
            mid = (low + high) / 2; 
            if (key < a[mid][col]) {
                high = mid;   
            } else if (key > a[mid][col]) {
                low = mid + 1;
            } else {
                return mid;   
            }
        }
        if(key > a[low][col])
            return -(low + 1);
        else
            return -low;
    }

}