Ez az oktatóanyag megtanulja, hogyan alkalmazhatunk bináris keresési algoritmust Python használatával, hogy megtaláljuk egy elem indexpozícióját az adott listában.
Bevezetés
A bináris keresés egy algoritmus egy adott elem megkeresésére a listában. Tegyük fel, hogy van egy ezer elemből álló listánk, és meg kell kapnunk egy adott elem indexpozícióját. A bináris keresési algoritmus segítségével nagyon gyorsan megtaláljuk az elem indexpozícióját.
Számos keresési algoritmus létezik, de ezek közül a bináris keresés a legnépszerűbb.
A bináris keresési algoritmus alkalmazásához a lista elemeit rendezni kell. Ha az elemek nincsenek rendezve, először rendezze őket.
Értsük meg a bináris keresés fogalmát.
A bináris keresés fogalma
A bináris keresési algoritmusban a következő módszerekkel találhatjuk meg az elem pozícióját.
Az ls parancsot ad a linuxnak
- Rekurzív módszer
- Iteratív módszer
Az oszd meg és uralkodj megközelítési technikát a rekurzív módszer követi. Ebben a módszerben egy függvényt újra és újra meghívnak, amíg nem talál egy elemet a listában.
hogyan lehet tudni a kijelző méretét
Egy utasításkészletet többször megismételnek, hogy megtalálják az elem indexpozícióját az iteratív módszerben. A míg ciklust használják ennek a feladatnak a végrehajtására.
A bináris keresés hatékonyabb, mint a lineáris keresés, mert nem kell minden listaindexet keresnünk. A listát rendezni kell a bináris keresési algoritmus eléréséhez.
Lépésről lépésre valósítsuk meg a bináris keresést.
Rendezett elemlistánk van, és a 45-ös indexpozíciót keressük.
[12, 24, 32, 39, 45, 50, 54]
Tehát két mutatót állítunk be a listánkban. Egy mutatót használunk a kisebb hívott érték jelölésére alacsony a második mutató pedig a legmagasabb hívott értéket jelöli magas .
Ezután kiszámítjuk az értékét középső elem a tömbben.
mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)
Most összehasonlítjuk a keresett elemet a középső indexértékkel. Ebben az esetben, 32 nem egyenlő Négy öt. Tehát további összehasonlítást kell végeznünk az elem megtalálásához.
Ha a keresett szám egyenlő a mid. Aztán vissza középső ellenkező esetben lépjen a további összehasonlításra.
tesztelés típusai
A keresendő szám nagyobb, mint a középső számot, összehasonlítjuk a n az elemek középső elemével a jobb oldalon középső és alacsonyra állítva alacsony = közép + 1.
Ellenkező esetben hasonlítsa össze a n a ... val középső elem bal oldalán lévő elemek közül középső és állítsa be magas nak nek magas = közép - 1.
Ismételje addig, amíg meg nem találja a keresett számot.
Bináris keresés megvalósítása Pythonban
Először egy bináris keresést valósítunk meg iteratív módszerrel. Megismételünk egy állításkészletet, és a lista minden elemét megismételjük. A középső értéket a keresés befejezéséig találjuk.
mennyit nyom a kat timpf
Értsük meg az iteratív módszer alábbi programját.
Python megvalósítás
# 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'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'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('Element is present at index', str(res)) else: print('Element is not present in list1') </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'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></=> Magyarázat:
A fenti programban -
- Létrehoztunk egy függvényt binary_search() függvény, amely két argumentumot vesz fel: egy listát rendezni kell, és egy számot kell keresni.
- Két változót deklaráltunk a lista legalacsonyabb és legmagasabb értékeinek tárolására. Az alacsony kezdeti értéke 0 lesz, magas nak nek len(lista1) - 1 és közép 0.
- Ezt követően kijelentettük a míg hurok azzal a feltétellel, hogy a legalacsonyabb egyenlő és kisebb, mint a legmagasabb A while ciklus ismétlődik, ha a szám még nem található.
- A while ciklusban megtaláljuk a középértéket, és összehasonlítjuk az indexértéket a keresett számmal.
- Ha a középindex értéke kisebb, mint n , a középértéket 1-gyel növeljük és hozzárendeljük A keresés bal oldalra mozog.
- Ellenkező esetben csökkentse a középértéket, és rendelje hozzá a magas . A keresés a jobb oldalra lép.
- Ha az n egyenlő a középértékkel, akkor térjen vissza középső .
- Ez addig fog történni, amíg a alacsony egyenlő és kisebb, mint a magas .
- Ha a függvény végére érünk, akkor az elem nem szerepel a listában. A -1-et visszaadjuk a hívó függvényhez.
Ismerjük meg a bináris keresés rekurzív módszerét.
Rekurzív bináris keresés
A rekurziós módszer használható a bináris keresésben. Ebben egy rekurzív függvényt fogunk definiálni, amely addig hívja magát, amíg nem teljesíti a feltételt.
mi az obj a java-ban
Értsük meg a fenti programot a rekurzív függvény segítségével.
Python program
# 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')
Kimenet:
Element is present at index 2
Magyarázat
A fenti program hasonló az előző programhoz. Deklaráltunk egy rekurzív függvényt és annak alapfeltételét. A feltétel az, hogy a legalacsonyabb érték kisebb vagy egyenlő a legmagasabb értékkel.
- A középső számot úgy számítjuk ki, mint az előző programban.
- Használtuk a ha utasítást a bináris keresés folytatásához.
- Ha a középső érték megegyezik a keresett számmal, akkor a középső érték kerül visszaadásra.
- Ha a középső érték kisebb, mint az érték, akkor a rekurzív függvényünket nézzük binary_search() ismét növelje a középértéket eggyel, és rendelje hozzá az alacsony értékhez.
- Ha a középső érték nagyobb, mint a keresett érték, akkor a rekurzív függvényünk binary_search() és csökkentse eggyel a középértéket, és rendelje hozzá az alacsony értékhez.
Az utolsó részben megírtuk a fő programunkat. Ugyanaz, mint az előző program, de az egyetlen különbség az, hogy két paramétert adtunk át a binary_search() funkció.
Ennek az az oka, hogy a rekurzív függvényben nem tudjuk hozzárendelni a kezdeti értékeket az alacsony, magas és középértékekhez. Minden alkalommal, amikor a rekurzív meghívásra kerül, ezeknek a változóknak az értéke visszaáll. Ez rossz eredményt fog adni.
Bonyolultság
A bináris keresési algoritmus összetettsége az O(1) a legjobb esetben. Ez akkor történik, ha a keresett elem az első összehasonlításban megtalálható. A O(bejelentkezés) a bináris keresés legrosszabb és átlagos összetettsége. Ez attól függ, hány keresést végeznek a keresett elem megtalálásához.
Következtetés
A bináris keresési algoritmus a leghatékonyabb és leggyorsabb módja egy elem keresésének a listában. Kihagyja a felesleges összehasonlítást. Ahogy a név is sugallja, a keresés két részre oszlik. A lista oldalára összpontosít, amely közel áll a keresett számhoz.
Mindkét módszert tárgyaltuk az adott szám indexpozíciójának meghatározására.