Овај водич ће научити како можемо да применимо алгоритам бинарног претраживања користећи Питхон да пронађемо индексну позицију елемента на датој листи.

Увод

Бинарно претраживање је алгоритам за проналажење одређеног елемента на листи. Претпоставимо да имамо листу од хиљаду елемената и да морамо да добијемо индексну позицију одређеног елемента. Можемо врло брзо пронаћи индексну позицију елемента користећи алгоритам бинарне претраге.

Постоји много алгоритама за претраживање, али бинарна претрага је најпопуларнија међу њима.

Елементи на листи морају бити сортирани да би се применио алгоритам бинарне претраге. Ако елементи нису сортирани, прво их сортирајте.

Хајде да разумемо концепт бинарне претраге.

Концепт бинарног претраживања

У алгоритму бинарне претраге можемо пронаћи позицију елемента користећи следеће методе.

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

Технику приступа завади па владај прати рекурзивни метод. У овој методи, функција се позива сама изнова и изнова док не пронађе елемент на листи.

Скуп наредби се понавља више пута да би се пронашла позиција индекса елемента у итеративној методи. Тхе док петља се користи за постизање овог задатка.

Бинарна претрага је ефикаснија од линеарне јер не морамо да претражујемо сваки индекс листе. Листа мора бити сортирана да би се постигао алгоритам бинарног претраживања.

Хајде да имплементирамо бинарну претрагу корак по корак.

Имамо сортирану листу елемената и тражимо индексну позицију 45.

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

Дакле, постављамо два показивача на нашој листи. Један показивач се користи за означавање мање вредности која се зове ниско а други показивач се користи за означавање највеће вредности тзв висока .

претварање стринга у инт јава

Затим израчунавамо вредност средњи елемент у низу.

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

Сада ћемо упоредити тражени елемент са средњом вредношћу индекса. У овом случају, 32 није једнако Четири, пет. Дакле, морамо да урадимо даље поређење да бисмо пронашли елемент.

Ако је број који тражимо једнак средини. Онда се врати мид иначе пређите на даље поређење.

Број за претрагу је већи од броја средњи број, упоређујемо н са средњим елементом елемената на десној страни од мид и ниско постављен на низак = средњи + 1.

Иначе, упоредите н са средњи елемент елемената на левој страни мид и сет висока до висока = средња - 1.

Понављајте све док се не пронађе број који тражимо.

Имплементирајте бинарну претрагу у Питхон-у

Прво, имплементирамо бинарну претрагу итеративном методом. Поновићемо скуп исказа и поновићемо сваку ставку листе. Пронаћи ћемо средњу вредност док се претрага не заврши.

Хајде да разумемо следећи програм итеративне методе.

Питхон имплементација

 # 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></=>

Објашњење:

У горњем програму -

• Направили смо функцију под називом бинари_сеарцх() функција која узима два аргумента - листу за сортирање и број за претрагу.
• Декларисали смо две променљиве за чување најниже и највише вредности на листи. Најнижем се додељује почетна вредност 0, висока до лен(лист1) - 1 и средина као 0.
• Затим смо прогласили док петљу са условом да је најниже је једнак и мањи од највиши Док петља ће се понављати ако број још није пронађен.
• У вхиле петљи налазимо средњу вредност и упоређујемо вредност индекса са бројем који тражимо.
• Ако је вредност средњег индекса мања од н , повећавамо средњу вредност за 1 и додељујемо је Претрага се помера на леву страну.
• У супротном, смањите средњу вредност и доделите је висока . Претрага се помера на десну страну.
• Ако је н једнако средњој вредности онда вратите мид .
• Ово ће се десити до ниско је једнак и мањи од висока .
• Ако дођемо до краја функције, онда елемент није присутан на листи. Враћамо -1 функцији која позива.

Хајде да разумемо рекурзивни метод бинарног претраживања.

Рекурзивно бинарно претраживање

Метода рекурзије се може користити у бинарној претрази. У овоме ћемо дефинисати рекурзивну функцију која наставља да позива саму себе док не испуни услов.

јава референтни типови

Хајде да разумемо горњи програм користећи рекурзивну функцију.

Питхон програм

 # 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 

Објашњење

Горе наведени програм је сличан претходном програму. Декларисали смо рекурзивну функцију и њен основни услов. Услов је да је најмања вредност мања или једнака највишој вредности.

• Израчунавамо средњи број као у последњем програму.
• Користили смо ако изјава за наставак бинарног претраживања.
• Ако је средња вредност једнака броју који тражимо, враћа се средња вредност.
• Ако је средња вредност мања од вредности, онда тражимо нашу рекурзивну функцију бинари_сеарцх() поново и повећајте средњу вредност за један и доделите ниској.
• Ако је средња вредност већа од вредности коју тражимо, онда је наша рекурзивна функција бинари_сеарцх() поново и смањите средњу вредност за један и доделите је ниској.

У последњем делу смо написали наш главни програм. Исти је као и претходни програм, али једина разлика је у томе што смо пренели два параметра у бинари_сеарцх() функција.

То је зато што не можемо да доделимо почетне вредности ниском, високом и средњем у рекурзивној функцији. Сваки пут када се позове рекурзивна вредност ће се ресетовати за те променљиве. То ће дати погрешан резултат.

Сложеност

Сложеност алгоритма бинарног претраживања је О(1) за најбољи случај. Ово се дешава ако елемент који тражимо нађемо у првом поређењу. Тхе О(пријава) је најгора и просечна сложеност случаја бинарне претраге. Ово зависи од броја претрага које се спроводе да бисмо пронашли елемент који тражимо.

Закључак

Бинарни алгоритам претраге је најефикаснији и најбржи начин претраживања елемента на листи. Прескаче непотребно поређење. Као што назив говори, претрага је подељена на два дела. Фокусира се на страну листе, која је близу броја који тражимо.

Разговарали смо о обе методе за проналажење индексне позиције датог броја.