What is the most efficient way to search users by their display name?

I think you should use the default class for this job – WP_User_Query.
The query have a lot of possibilities, also get the display name. WP_User_Query is a class that allows querying WordPress database tables _users and _usermeta.

Also it is helpful when you use a cache for the values. Also here I prefer the WordPress defaults WP_Cache (Non-Persistent Cache) or transient API (Database-Driven Temporarily Persistent Cache).

The example below will demonstrate this with WP_Cache, you can also doing this with transients. The code will not work, is only write by scratch to illustrate.

function wpse_get_user_data( $args ) {


    if ( ! $user_query = wp_cache_get( $args->ID, 'your_key' ) ) {
        $user_query = array();
        $user_query = new WP_User_Query( $args );

        wp_cache_add( $args-ID, $user_query, 'your_key' );
    }

    return $user_query;
}