Featured images are actually associated by ID, not URL. So, as long as when you move the images (I assume via FTP) you also update the image URL in the database, you won’t have to update any of the posts that use the images as a featured image.
WP stores the image URL as postmeta. So, for each attachment, you’ll need to find the post ID, then search for the _wp_attached_file postmeta key for that particular post ID. Once you find that, you can edit it to add in the year and month.
So you should find something like
_wp_attached_file = media/file.jpg
and change it to
_wp_attached_file = media/2018/06/file.jpg
if it should be in the June 2018 folder.
— But — if you also use any of these images anywhere in actual post content, that part does not automatically update. So, you would also have to update each individual post that contains these images (you should be able to search for them in phpmyadmin, or you could use your existing code to find all the urls and then build a regex to match any that don’t have the year and month in the URL, and add more code to determine what month and year they need to go in and update that value in the database too.