package web;

import java.util.Arrays;

/**
 * 有一個已經排序的數組（升序）， 數組中可能有正數、負數或0，求數組中元素的絕對值最小的數， 要求，不能用順序比較的方法 求絕對值最小的數
 * 
 * @author mayw
 */
public class FindMinValue {

    /**
     * 
     * @param source
     *            原數組
     * @return 絕對值最小的數
     * @throws Exception 
     */
    public static int[] getMinAbsoluteValue(final int[] source) throws Exception {
        int[] rvs = null;
        if(source==null){
            throw new Exception("非法的原數組, 對象為null");
        }
        int index = binarySearch(source,0);
        int insertPos = -1 - index;
        if(index >= 0){
            return new int[]{0}; // 存在0, 0絕對值最小 
        }else if(source.length==1){
            return new int[]{source[0]};
        }else if(insertPos == source.length){
            return new int[]{source[source.length - 1]};
        }else if(insertPos == 0){
            return new int[]{source[0]};
        }else if(Math.abs(source[insertPos]) > Math.abs(source[insertPos - 1])){
            return new int[]{source[insertPos - 1]};
        }else if(Math.abs(source[insertPos]) == Math.abs(source[insertPos - 1])){
            return new int[]{source[insertPos - 1],source[insertPos],};
        }else{
            return new int[]{source[insertPos]};
        }
//        int rv = index >= 0 ? 0
//                : source[insertPos == source.length ? source.length - 1
//                        : insertPos];
//        if(){
//            
//        }
//        return index >= 0 ? 0
//                : source[insertPos == source.length ? source.length - 1
//                : insertPos];
    }

    /**
     * 使用二分搜索法來搜索指定的 int 型數組，以獲得指定的值。
     * 
     * @param source
     *            要查找的目標數組
     * @param target
     *            要查找的數
     * @return 如果它包含在數組中，則返回搜索鍵的索引； 否則返回 (-(插入點) - 1)。 插入點
     *         被定義為將鍵插入數組的那一點：即第一個大于此鍵的元素索引， 如果數組中的所有元素都小于指定的鍵，則為 a.length。
     *         注意，這保證了當且僅當此鍵被找到時，返回的值將 >= 0。
     */
    public static int binarySearch(final int[] source, int target) {
        int low = 0;
        int high = source.length - 1;
        while(low<=high){
            int midIdx = (low+high)>>1; // 去中間索引
            int midVal = source[midIdx]; // 去中間值
            if(target < midVal){
                high = midIdx - 1; // 去中間索引的前半部分, 不包含中間索引
            }else if(target > midVal){
                low = midIdx + 1; // 去中間索引的后半部分, 不包含中間索引
            }else{
                return midIdx; // 返回當前索引
            }
        }
        return -low-1;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{0})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-1})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{1})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-1})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-1,1,2,3,4})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-1,2,3,4})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-2,1,3,4})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{1,2,3,4})));
    }

}

/* 參考 : http://www.w3school.com.cn/xmldom/dom_http.asp */
/*
 * 獲取ajax對象
 */
function getXmlHttpRequest(){
    var xhr = null;
    if(typeof(XMLHttpRequest) != 'undefined'){
        xhr = new XMLHttpRequest();
    }else{
        xhr = new ActiveXObject("Microsoft.XMLHttp");
    }
    return xhr;
}

/*
 * post方式請求
 */
function post(url, queryString,fn){
    var xhr = getXmlHttpRequest();
    xhr.open('post',url,true);
    xhr.setRequestHeader("Content-Type","application/x-www-form-urlencoded");
    xhr.onreadystatechange=function(){
        if(xhr.readyState == 4){
            if(xhr.status == 200){
                fn.apply(this,[xhr]);
            }
        }
    };
    xhr.send(queryString);
}

/*
 * get方式請求
 */
function get(url,fn){
    var xhr = getXmlHttpRequest();
    xhr.open('get',url,true);
    xhr.onreadystatechange=function(){
        if(xhr.readyState == 4){
            if(xhr.status == 200){
                fn.apply(this,[xhr]);
            }
        }
    };
    xhr.send(null);
}

 /*
  * 測試
  */
post("ajax","",function(xhr){
    alert(xhr.responseText);
});