После того как массив отсортирован, какой алгоритм/способ поиска можно применить, чтобы найти пользователя по ID быстрее линейного поиска?

Чтобы избежать вложенного перебора (O(n²)) при поиске пользователей по ID, можно использовать структуру данных с быстрым доступом по ключу, например, объект (Map) в JavaScript. Вместо того чтобы для каждого ID искать пользователя перебором, создаём словарь, где ключ — ID, а значение — пользователь. Тогда поиск будет O(1) для каждого ID, и общая сложность снизится до O(n).

Пример:

const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 3, name: 'Charlie' }
];

// Создаём Map для быстрого поиска
const userMap = new Map(users.map(user => [user.id, user]));

const idsToFind = [2, 3];
const foundUsers = idsToFind.map(id => userMap.get(id));
console.log(foundUsers); // [{id: 2, name: 'Bob'}, {id: 3, name: 'Charlie'}]

Такой подход значительно оптимизирует поиск.