Здравствуйте, меня зовут Косуке Кузуока, инженер-исследователь искусственного интеллекта в DeNA Co., Ltd. Я говорил об общих структурах данных и о том, как они работают в своих предыдущих постах. В этом сообщении в блоге я в основном расскажу об алгоритме поиска и дам вам хороший вопрос на собеседовании, который можно решить с помощью алгоритма поиска. Эта тема действительно важна, и ее часто задают на собеседованиях по кодированию. Если вы хорошо разбираетесь в этой теме, тогда вы сможете писать эффективное программное обеспечение, и у вас будет больше шансов на собеседованиях по кодированию!
Это сообщение в блоге предназначено для людей, которые хотят изучить основы темы CS, или для людей, которые готовятся к предстоящим собеседованиям по программированию. Если вы новичок в этой теме, возможно, вы захотите вернуться и прочитать мои предыдущие сообщения, чтобы понять терминологию и структуры данных, используемые в этом сообщении в блоге. Все ссылки на свои предыдущие посты я оставлю ниже. С учетом сказанного, давайте приступим!
- Часть 1: Что такое структуры данных и алгоритмы?
- Часть 2: Наиболее широко используемые структуры данных (массивы и связанные списки)
- Часть 3: Наиболее широко используемые структуры данных (стеки и очереди)
- Часть 4: Поиск и сортировка (двоичный поиск) *
- Часть 5: Поиск и сортировка (рекурсия и DP)
Что ищет?
Представим, что вы готовитесь к предстоящему собеседованию в ведущей технологической компании. Вам будут заданы вопросы об основах информатики. Теперь вы хотите просмотреть старую книгу по информатике из вашего класса колледжа. У вас есть куча книг, отсортированных по названиям на вашей книжной полке, и вы знаете, что книга, которую вы ищете, находится на книжной полке. Как в этой ситуации эффективно найти нужную книгу?
Самым простым решением этой проблемы было бы что-то вроде поиска названия по одному слева направо и прекращения поиска всякий раз, когда вы находите книгу с таким же названием. Большой! Вы придумали простой алгоритм поиска в реальной жизни! Алгоритм поиска в контексте информатики почти такой же, но вопрос будет примерно таким: «Учитывая список элементов A и элемент B, найдите B в A», и вы должны сделать это немного более эффективно. чем простой алгоритм.
Двоичный поиск: эффективный алгоритм поиска
Как и в приведенном выше примере, книги на книжной полке отсортированы по порядку, так что крайняя левая книга начинается с буквы «А», а самая правая книга начинается с буквы «Z». Вы также знаете, что название вашей книги начинается с буквы «G» - «Grokking the Computer Science» или что-то в этом роде. Что, если вы разделите книги пополам и поищите первую букву в средней книге. Если первая буква средней книги, скажем, «М», то можно сказать, что нет смысла смотреть в правую половину книг, потому что «Г» не попадает в диапазон от «М». на «Z». Вы можете представить, как применяете эту технику, пока не останется только одна книга, и она не станет той, которую вы ищете. Именно так работает бинарный поиск. Давайте посмотрим на рисунок ниже, чтобы визуально понять этот алгоритм!
Я немного упростил пример, чтобы он соответствовал диаграмме. Книги в списке (или на книжной полке) представлены первой буквой названия, а книга, которую вы ищете, начинается с буквы «G». Как я описал в предыдущем разделе, мы сначала ищем среднюю книгу и сравниваем первую букву заголовков. Затем разрезаем пополам по сравнению их букв. По сути, мы делаем одно и то же неоднократно, пока не останется только одна книга, и это должна быть та, которую мы ищем. Поначалу это может показаться немного устрашающим, но если вы последуете инструкциям на нескольких примерах, то это будет более интуитивно понятно, поверьте мне!
Теперь давайте посмотрим на реализацию на Python. Главное здесь - сначала запомнить начальный и конечный индексы всего массива, а затем обновить начальный и конечный индексы в соответствии со средним значением. Условие остановки здесь - когда начальный индекс равен конечному индексу - это означает, что они указывают на один и тот же элемент.
Здесь у нас есть функция, которая выполняет двоичный поиск. Входными данными функции является список целых чисел и целочисленное значение для поиска в списке. Первое, что мы делаем, это получаем первый и последний индекс списка в строке 12, а затем разрезаем его пополам для каждой итерации с помощью цикла while - обновляя low и high с средним значением в строках 21 и 23. Ключом для реализации выше является то, как мы обновляем переменные low и high, представляющие левый и правый указатели соответственно. Если среднее значение больше, чем значение, тогда мы знаем, что наше значение находится в левой половине, поэтому мы обновляем правый указатель, чтобы он указывал на середину в строке 23. Если это не так, то мы знаем, что наше значение находится в в правой половине, поэтому мы обновляем левый указатель в строке 21. Таким образом мы разрезаем массив пополам каждый раз.
Теперь поговорим о сложности выполнения этого алгоритма. Поскольку мы разрезаем список пополам для каждой итерации, время выполнения становится O (log (N)) - log base 2, а не 10. Если вы хотите доказать это самостоятельно, просто представьте, что у вас изначально есть 8 элементов в списке, и в следующий раз вы разрежете его пополам, чтобы список стал длиной 4, и делайте то же самое снова и снова. Когда вы разрезаете его пополам в третий раз, список становится равным 1, и алгоритм завершается. Это потому, что log (8) равен 3, и это верно для любого числа.
Давайте сравним эффективность двоичного поиска и простого линейного поиска. Я произвольно создавал массивы разных размеров, а затем выполнял линейный и бинарный поиск по ним. Дело здесь не в измерении точного времени выполнения обоих алгоритмов поиска, а в сравнении эффективности обоих алгоритмов. Посмотрим!
Похоже, двоичный поиск намного эффективнее линейного поиска. На самом деле двоичный поиск выглядит как постоянное время, но это не так. Это похоже на постоянное время, потому что линейный поиск занимает слишком много времени, но если мы увеличим производительность двоичного поиска, то он должен выглядеть как логарифмическая функция.
Так что двоичный поиск работает хорошо и довольно эффективно. Кратко поговорим о его ограничениях. Бинарный поиск работает, если список отсортирован. Если список не отсортирован, вы все равно можете выполнить двоичный поиск после сортировки списка, но наиболее эффективная сортировка списка будет похожа на O (N * log (N)), поэтому на самом деле это хуже, чем линейный поиск - линейный поиск работает в линейном режиме или O (N), отсюда и название. Теперь мы знаем, когда двоичный поиск может быть хорошим кандидатом, а когда нет. Давайте рассмотрим случай, когда двоичный поиск действительно эффективен!
Время вопросов для собеседования!
Я дам вам хороший вопрос по кодированию, который я нашел на LeetCode, который можно решить с помощью того, что вы узнали из этого сообщения в блоге. Попробуйте сначала применить полученные знания. Если вы не можете решить эту проблему эффективно, поищите подсказки, которые я оставил внизу сообщения. Удачи!
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: - Integers in each row are sorted from left to right. - The first integer of each row is greater than the last integer of the previous row. Example 1: Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true
Подсказка 1. Учитывая m строк, как вы можете эффективно решить, в какой строке, возможно, находится целевое значение?
Подсказка 2: учитывая n элементов в строке, которые вы получаете при вертикальном сканировании, как вы можете эффективно искать целевое значение?
Если вы решили этот вопрос и хотите сравнить с моим решением, посетите эту ссылку на Github, чтобы вы могли проверить мое решение, которое я придумал, используя эффективный алгоритм поиска. Если у вас есть какие-либо вопросы о моем решении или вы придумали еще более эффективное решение, оставьте мне комментарий в этом сообщении, чтобы я мог проверить его позже!
Заключение
В этом сообщении в блоге я рассказал об эффективном алгоритме поиска и о том, как мы можем его реализовать. Затем мы рассмотрели проблему, в которой мы можем применить наши знания для ее эффективного решения. Всякий раз, когда я вижу такое утверждение, как «заданный отсортированный массив, выполнить X», я всегда спрашиваю себя, могу ли я применить двоичный поиск для его решения. Это очень хорошая отправная точка для решения вопроса, и я настоятельно рекомендую вам сделать то же самое, если вы готовитесь к предстоящим собеседованиям по кодированию.
Спасибо, что прочитали это сообщение в блоге. Надеюсь, это помогло вам понять, как работает двоичный поиск и когда его следует применять. В следующем посте я расскажу об алгоритмах сортировки и, как всегда, реализую их на Python. Я оставлю вопрос для собеседования и в следующем посте, чтобы вы могли применить свои знания к настоящему вопросу кодирования. Я также поделюсь своим решением на эти вопросы, чтобы вы могли сравнить его с вашим. Я очень надеюсь, что вам понравился этот пост в блоге! Если да, пожалуйста, оставьте несколько аплодисментов, и я увижу вас в следующем посте: D
