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

Въведение

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

Има много алгоритми за търсене, но двоичното търсене е най-популярно сред тях.

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

Нека разберем концепцията за двоично търсене.

Концепция за двоично търсене

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

• Рекурсивен метод
• Итеративен метод

Техниката на подхода „разделяй и владей“ е последвана от рекурсивния метод. При този метод функцията се извиква отново и отново, докато намери елемент в списъка.

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

1 милион номер

Двоичното търсене е по-ефективно от линейното търсене, защото не е необходимо да търсим във всеки индекс на списък. Списъкът трябва да бъде сортиран, за да се постигне алгоритъмът за двоично търсене.

Нека направим стъпка по стъпка внедряване на двоично търсене.

Имаме сортиран списък с елементи и търсим позицията на индекса 45.

[12, 24, 32, 39, 45, 50, 54]

И така, задаваме два указателя в нашия списък. Един указател се използва за обозначаване на по-малката извикана стойност ниско а вторият указател се използва за обозначаване на най-високата извикана стойност Високо .

какво е ini за работния плот

След това изчисляваме стойността на средата елемент в масива.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer) 

Сега ще сравним търсения елемент със средната стойност на индекса. В такъв случай, 32 не е равно на Четири пет. Така че трябва да направим допълнително сравнение, за да намерим елемента.

Ако числото, което търсим, е равно на средата. След това се върнете средата в противен случай преминете към по-нататъшното сравнение.

Числото за търсене е по-голямо от средата номер, сравняваме н със средния елемент на елементите от дясната страна на средата и задайте ниско на ниско = средно + 1.

В противен случай сравнете н с среден елемент на елементите от лявата страна на средата и задайте Високо да се високо = средно - 1.

Повторете, докато номерът, който търсим, бъде намерен.

Приложете двоично търсене в Python

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

javascript коментар

Нека разберем следната програма на итеративния метод.

Внедряване на Python

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

Обяснение:

В горната програма -

• Създадохме функция, наречена binary_search() функция, която приема два аргумента - списък за сортиране и число за търсене.
• Декларирахме две променливи за съхраняване на най-ниската и най-високата стойност в списъка. Ниската е присвоена първоначална стойност на 0, Високо да се len(list1) - 1 и средата като 0.
• След това сме декларирали докато цикъл с условието, че най-нисък е равен и по-малък от най-високо Цикълът while ще повтори, ако номерът все още не е намерен.
• В цикъла while намираме средната стойност и сравняваме стойността на индекса с числото, което търсим.
• Ако стойността на средния индекс е по-малка от н , увеличаваме средната стойност с 1 и я присвояваме на Търсенето се премества вляво.
• В противен случай намалете средната стойност и я присвоете на Високо . Търсенето се премества в дясната страна.
• Ако n е равно на средната стойност, тогава се връща средата .
• Това ще стане до ниско е равен и по-малък от Високо .
• Ако стигнем до края на функцията, значи елементът не присъства в списъка. Връщаме -1 на извикващата функция.

Нека разберем рекурсивния метод на двоично търсене.

Рекурсивно двоично търсене

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

Нека разберем горната програма с помощта на рекурсивната функция.

Програма Python

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') 

Изход:

 Element is present at index 2 

Обяснение

Горната програма е подобна на предишната програма. Декларирахме рекурсивна функция и нейното основно условие. Условието е най-ниската стойност да е по-малка или равна на най-високата стойност.

• Изчисляваме средното число, както в последната програма.
• Ние сме използвали ако оператор, за да продължите с двоичното търсене.
• Ако средната стойност е равна на числото, което търсим, се връща средната стойност.
• Ако средната стойност е по-малка от стойността, тогава търсим нашата рекурсивна функция binary_search() отново и увеличете средната стойност с едно и задайте ниска.
• Ако средната стойност е по-голяма от стойността, която търсим, тогава нашата рекурсивна функция binary_search() отново и намалете средната стойност с едно и я задайте на ниска.

В последната част написахме нашата основна програма. Тя е същата като предишната програма, но единствената разлика е, че сме предали два параметъра в binary_search() функция.

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

Сложност

Сложността на алгоритъма за двоично търсене е О(1) за най-добрия случай. Това се случва, ако елементът, който търсим, намери в първото сравнение. The O(вход) е най-лошият и средният случай на сложност на двоичното търсене. Това зависи от броя на търсенията, които се извършват, за да се намери елементът, който търсим.

java е следващият

Заключение

Алгоритъмът за двоично търсене е най-ефективният и бърз начин за търсене на елемент в списъка. Пропуска ненужното сравнение. Както подсказва името, търсенето е разделено на две части. Той се фокусира върху страната на списъка, която е близо до номера, който търсим.

Обсъдихме и двата метода за намиране на позицията на индекса на даденото число.