function binary_search(A, target){
    let lo = 1, hi = A.length;
    while (lo <= hi){
        let mid = lo + (hi - lo) / 2;
        if (A[mid] == target){
            return mid;
        } else if (A[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
}