Arrays2D

Arrays2D.java

  /**
   * Searches a 2D array sorted by row and col in logarithmic time. 
   */
  public static boolean contains(int[][] A, int elem){
    int R = A.length-1;
    int C = A[0].length-1;
    return contains(A, elem, 0, R, 0, C);
  }

  private static boolean contains(int[][] A, int elem, int xmin, int xmax,
      int ymin, int ymax){
    
    if(isOutOfBounds(A, xmin, xmax, ymin, ymax)){return false;}
    if(xmin > xmax || ymin > ymax){return false;}
    if(elem < A[xmin][ymin] || elem > A[xmax][ymax]){return false;} //EARLY EXIT

    if(isSingleton(xmin, xmax, ymin, ymax)){
      return elem == A[xmin][ymin];
    }

    int xmid = (xmin + xmax)/2;
    int ymid = (ymin + ymax)/2;

    if(elem < A[xmid][ymid]){
      return contains(A, elem, xmin, xmid-1, ymin, ymax)
          ||  contains(A, elem, xmid, xmax, ymin, ymid-1);
    }
    else if(elem > A[xmid][ymid]){
      return contains(A, elem, xmid+1, xmax, ymin, ymax)
          ||  contains(A, elem, xmin, xmid, ymid+1, ymax);
    }
    else{
      return true;
    }
  }

  private static boolean isOutOfBounds(int[][] A, int xmin, int xmax, int ymin, int ymax){
    if(xmin < 0 || xmin >= A.length || xmax < 0 || xmax >= A.length ||
        ymin < 0 || ymin >= A[0].length || ymax < 0 || ymax >= A[0].length){return true;}
    return false;
  }

  private static boolean isSingleton(int xmin, int xmax, int ymin, int ymax){
    return (xmax - xmin == 0) &&
        (ymax - ymin == 0);
  }