Още един алгоритъм за двоично търсене

Задълбочен поглед върху алгоритъма и някои изводи за следващото ви техническо интервю

Да предположим, че сте в библиотека и искате да намерите книга на определена лавица. Книгата е подредена по азбучен ред или по някакъв целочислен код.

Най-общо казано, наивният начин да го намерите е да разглеждате книга по книга, но това ще отнеме много време. Мислите, че трябва да има по-добро решение.

Ta Ta！

Алгоритъм за двоично търсене!

Двоично търсене

В компютърните науки двоичното търсене, известно още като търсене с половин интервал, е алгоритъм за търсене, който намира позицията на цел стойност в рамките на сортиран масив.

Алгоритъмът за двоично търсене се използва за търсене на елемент от сортиран/сортиран набор. Работи, като сравнява целевата стойност със средния елемент на масива.

Изглежда, че този алгоритъм е малко абстрактен и далеч от основното ни познание. Но ние го използваме много в реалния си живот, без дори да го осъзнаваме. Ако имате интерес, моля, разгледайте следните публикации.

Основен проблем

Сега нека разгледаме задълбочено алгоритъма с проблем, за да го разберем по-добре.

Изявление на проблема:

Даден е масив от цели числа nums, който е сортиран въввъзходящ ред, и цяло число target, напишете функция за търсене target в nums. Ако target съществува, върнете неговия индекс. В противен случай върнете -1.

Пример:

Input: nums = [-1,0,3,5,9,12], target = 5
Output: 3
Explanation: 5 exists in nums and its index is 3

Кодово решение:

class Solution:
    
    def search(self, nums, target):
        left, right = 0, len(nums)-1                     # line 1
        while left <= right:
            pivot = left + (right-left)//2               # line 2
            
            if nums[pivot] == target:                    # line 3
                return pivot
            elif nums[pivot] < target:                   # line 4     
                left = pivot + 1    
            else:                                        # line 5
                right = pivot - 1                          
         
        return -1

Обяснение:

1. Инициализираме левия и десния показалец (ред 1)
2. Изчислете средния въртящ се показалец (ред 2)
3. Тъй като nums[pivot] е по-малък от целта, актуализираме левия показалец до по-нова стойност (ред 4)
4. Актуализиране на средния въртящ се показалец (ред 2)
5. Тъй като nums[pivot] е по-голямо от целта, актуализираме десния указател до по-нова стойност (ред 5)
6. Актуализирайте отново средния въртящ се показалец (ред 2)
7. nums[pivot] равен на целевата стойност този път, ние приключваме! (ред 3)

Ключови изводи:

• Актуализация на показалеца: преместете левия показалец вдясно от опорната точка: left = pivot + 1 , преместете десния показалец вляво от опорната точка: right = pivot - 1
• Условие за повторение: while left ≤ right
• Обобщен индекс: pivot = left + (right-left)//2

Проблем с вариантите

За да разбера по-добре алгоритмите за двоично търсене, подготвям някои проблеми с вариантите.

1. „Познай по-голямо или по-малко число“
2. Позиция за вмъкване на търсене — LeetCode
3. Търсене на 2D матрица
4. „Намиране на пиков елемент“
5. Намиране на минимум в завъртян сортиран масив
6. Sqrt(x)