<div id="notfound">Ничего не найдено</div>

div#notfound{
    display:none;
}

function myFunction() {
    // Declare variables
    //добавляем счетчик найденного
    found=0;
    var input, filter, ul, li, a, i;
    input = document.getElementById('myInput');
    filter = input.value.toUpperCase();
    ul = document.getElementById("myUL");
    li = ul.getElementsByTagName('li');
    notfound=document.getElementById("notfound");
    notfound.style.display="none";//скроем если при предыдущем цикле блок был показан

    // Loop through all list items, and hide those who don't match the search query
    for (i = 0; i < li.length; i++) {
        a = li[i].getElementsByTagName("a")[0];
        if (a.innerHTML.toUpperCase().indexOf(filter) > -1) {
            found++;
            li[i].style.display = "";
        } else {
            li[i].style.display = "none";
        }

    }
    if(found==0){
        //если ничего не найдено покажем блок "Ничего не найдено"
        document.getElementById("notfound").style.display="block";
    }
}