In Google Chrome. It doesn't fully clean the search history. I have to open chrome and go to options, Under the Bonnet, Clean browsing data. Then it's finished.
P.S If this has already been a topic then I apologise. But I don't know the technical stuff to recognise the topic.