Cortana is embedded software, removing Cortana from your computer will cause important functions to stop working, with one of those being Windows' built-in search feature.
You can remove Phone App, map etc. through PowerShell commands.
Right-click on the Start button and click on Run. In Run Command window, type regedit and click on OK.
Navigate to HKEY_CURRENT_USER\Software\Policies\Microsoft\Windows and create a New Key by right-clicking on Windows and choosing New > Key in the contextual menus.
Name the New Key as Explorer.
Next, right-click on Explorer select New > DWORD (32-bit) Value in the contextual menu. Name this newly created DWORD as “DisableSearchBoxSuggestions” and hit the Enter Key.
Now, Double-click on newly created DisableSearchBoxSuggestions DWORD.
In the pop-up, change the Data Value for DisableSearchBoxSuggestions to 1 and click on OK.
Reboot.