| dbpprop:abstract
|
- In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the middle element is equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the middle element. The method reduces the number of elements needed to be checked by a factor of two each time, and finds the target value, if it exists in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm. Viewing the comparison as a subtraction of the sought element from the middle element,{{Citation needed|date=August 2009 only the sign of the difference is inspected: there is no attempt at an interpolation search based on the size of the difference.
- Die binäre Suche ist ein Algorithmus, der auf einem Array recht schnell ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente des Array in einer dem Suchbegriff entsprechenden Weise sortiert sind. Der Algorithmus basiert auf dem Schema Teile und Herrsche.
- Binární vyhledávání (nebo také metoda půlení intervalu) je vyhledávací algoritmus na nalezení zadané hodnoty v uspořádaném seznamu pomocí zkracování seznamu o polovinu v každém kroku. Binární vyhledávání najde medián, porovná s hledanou hodnotou a na základě výsledku porovnání se rozhodne o pokračování v horní nebo dolní části seznamu a rekurzivně pokračuje od začátku. Binární vyhledávání je algoritmus s logaritmickou časovou složitostí O(log n). Přesněji, je potřeba <math>1 + \log_2 N {}</math> iterací na získání výsledku. Je značně rychlejší než lineární vyhledávání, které má časovou složitost O(n). Nicméně vyžaduje, aby data byla setříděna, je tudíž vhodný jen pro určitou množinu problémů. Dá se vyjádřit rekurzivně i iterativně; ve většině programovacích jazycích je však rekurzivní zápis mnohem elegantnější. Iterativní varianta algoritmu je však (díky absenci režie související s voláním funkcí) mírně rychlejší. Binární vyhledávání je příkladem algoritmu typu rozděl a panuj.
- Puolitushaku on tietojenkäsittelytieteessä tehokas ja yleisesti käytetty hakualgoritmi tiedon etsimiseen järjestetystä taulukosta. Puolitushaun ideana on etsiä etsittävää alkiota taulukon keskeltä, ja mikäli alkiota ei löytynyt, voidaan alkion etsimistä jatkaa alkuperäisen taulukon alku- tai loppupään puolivälistä riippuen siitä onko haettava arvo pienempi vai suurempi kuin taulukon keskellä oleva alkio. Koska jokainen hakuaskel puolittaa taulukon josta alkiota haetaan, on algoritmin asymptoottinen suoritusaika O(log n), missä n on alkioiden lukumäärä. Voidaan osoittaa, että tätä asymptoottisesti nopeampaa vertailuihin perustuvaa algoritmia etsiä alkio taulukosta ei ole. Seuraava puolitushaun pseudokoodi palauttaa indeksin josta alkio löytyy: Puolitushaku(taulu, haettava, vasen, oikea) while vasen ≤ oikea keski ← (vasen+oikea)/2 if taulu[keski] = haettava return keski if haettava < taulu[keski] oikea ← keski-1 else vasen ← keski+1 return null Koska yllä oleva algoritmi ei käytä rekursiota, on muistivaatimus yllä olevassa toteutuksessa O(1) eli algoritmi vaatii vain vakiomäärän muistia. Käytännössä moni ohjelmoija tekee virheen kirjoittaessaan (vasen + oikea) / 2, sillä useimmissa ohjelmointikielissä kokonaislukuarvo vasen + oikea voi pyörähtää tällöin ympäri. Oikea ratkaisu on kirjoittaa esimerkiksi vasen + (/ 2).
- La dichotomie (« couper en deux » en grec) est, en algorithmique, un processus itératif ou récursif de recherche où, à chaque étape, l'espace de recherche est restreint à l'une des deux parties. On suppose bien sûr qu'il existe un test relativement simple permettant à chaque étape de déterminer l'une des deux parties dans laquelle se trouve une solution. Pour optimiser le nombre d'itérations nécessaires, on s'arrangera pour choisir à chaque étape deux parties sensiblement de la même « taille » (pour un concept de « taille » approprié au problème), le nombre total d'itérations nécessaires à la complétion de l'algorithme étant alors logarithmique en la taille totale du problème initial. L'algorithme s'applique typiquement à la recherche d'un élément dans un ensemble fini ordonné et organisé en séquence. La fonction de « taille » du problème sera alors le cardinal de l'espace (fini) de recherche, et à chaque étape, on coupera l'espace de recherche en deux parties de même taille (à un élément près) de part et d'autre de l'élément médian. La dichotomie peut être vue comme une variante simplifiée de la stratégie plus générale diviser pour régner appliquée au cas particulier de la recherche itérative d'une solution, où le traitement des sous-espaces exclus de la recherche et de sa recombinaison peuvent être court-circuités.
- In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca per individuare un determinato valore all'interno di un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.
- 二分探索（にぶんたんさく、BS;Binary Search）とは検索のアルゴリズムの一つ。二分検索、バイナリサーチともいう。 ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。 大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。 n個のデータがある場合、時間計算量は<math>O(\log_2 n)</math>である（O記法）。 n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。
- Binærsøk er en effektiv algoritme for å finne fram til et bestemt element i en sortert liste ved å dele listen i to for hvert steg. Algoritmen tar det midterste elementet i den sorterte listen og sammenligner med det elementet en skal finne fram til for å finne ut om det er større eller mindre. Fordi listen er sortert vet en dermed om elementet kommer før eller etter, og søker deretter i den gjenstående halvdelen på samme måte. Her er pseudokode for en funksjon som ser på den verdien i den sorterte listen a som ligger midt mellom plasseringene left og right. Funksjonen kaller seg selv rekursivt med den ene halvdelen av listen. function binarySearch(a, value, left, right) if right < left return not found mid := floor(/2) if value > a[mid] return binarySearch(a, value, mid+1, right) else if value < a[mid] return binarySearch(a, value, left, mid-1) else return mid
- Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks. Np. jeśli tablica zawiera milion elementów, wyszukiwanie binarne musi sprawdzić maksymalnie 20 elementów (<math>\log_2{1\,000\,000} \approx 20</math>) w celu znalezienia żądnej wartości. Dla porównania wyszukiwanie liniowe wymaga w najgorszym przypadku przeglądnięcia wszystkich elementów tablicy.
- A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
- Algoritmul de căutare binară este un algoritm de căutare folosit pentru a găsi un element într-o listă ordonată(tablou unidimensional/vector). Algoritmul funcţionează pe baza tehnicii divide et impera. Valoarea căutată este comparată cu cea a elementului din mijlocul listei. Dacă e egală cu cea a acelui element, algoritmul se termină. Dacă e mai mare decât acea valoare, algoritmul se reia, de la mijlocul listei până la sfârşit, iar dacă e mai mică, algoritmul se reia pentru elementele de la începutul listei până la mijloc. Întrucât la fiecare pas cardinalul mulţimii de elemente în care se efectuează căutarea se înjumătăţeşte, algoritmul are complexitate logaritmică. Consideram un tablou unidomensional v de n elemente deja sortat, si trei variabile:i=inceput, s=sfarsit si m=mijloc. Metoda verifica de mai multe ori daca mijlocul vectorului/tabloului unidimensional este egala cu elementul cautat: ■in cazul in care este egala, variabila m reprezinta pozitia elementului in vector; ■daca nu se indeplineste conditia de egalitate se trece la verificarea pozitiei elementului cautat in vector astfel: daca elementul cautat este mai mic decat elementul din mijlocul vectorului, variabila "s" ia valuarea lui "m" iar daca nu variabila i ia valuarea lui m. Totul se repeta cat timp i este mai mic decat s.
- Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Также применяется для нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании.
- Binärsökning är en algoritm för att avgöra om en mängd innehåller ett givet element. Sökningen utförs i flera steg och i varje steg skall man utesluta att halva den kvarvarande mängden innhåller elementet och därmed kunna koncentrera sig på den andra halvan. Intervallhalveringsmetoden är en term som används om både binärsökning och den matematiska problemlösningsmetoden i Bolzanos sats. Ett exempel på binärsökning är uppslagning av ett ord eller namn i en alfabetiskt ordnad lista, till exempel en tryckt telefonkatalog eller en ordbok. Man börjar med att titta i mitten av listan. Genom att jämföra det sökta ordet med det som står i mitten av listan, vet man vilken halva av listan man ska fortsätta med. Efter andra uppslagningen återstår bara en fjärdedel av listan. Om hela listan har N uppslagsord, krävs högst <math>\lceil\log_2 N\rceil</math> uppslagsningar eller halveringar för att hitta rätt ställe, eller 2-logaritmen avrundad uppåt. Ett sätt att illustrera sökningen är som ett binärt sökträd där varje nod i trädet har maximalt två barn det ena måste vara större än och det andra mindre än nodens egna element. Alla noder i trädet är element i listan. Trädets höjd är högsta antalet uppslagningar som sökningen kräver.
- İkili Arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır. Bu teknikteki her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin orta değer tarafından ikiye ayrılan kısımlardan hangisinde olduğu kontrol edilir, aranan değeri içeren kısım bir sonraki adımda arama yapılacak dizi olur ve bu sayede arama yapılan listedeki eleman sayısı her adımda yarıya indirilmiş olur. Bu algoritma ile N elemanlı bir dizide en fazla <math>\lceil\log_2 N\rceil</math> karşılaştırma yaparak aranan değerin yerini bulmak mümkündür.
- Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння. Трудомісткість алгоритму <math>1 + \log_2 n</math>, де n — кількість елементів у масиві.
|
| rdfs:comment
|
- In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the middle element is equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the middle element.
- Die binäre Suche ist ein Algorithmus, der auf einem Array recht schnell ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente des Array in einer dem Suchbegriff entsprechenden Weise sortiert sind. Der Algorithmus basiert auf dem Schema Teile und Herrsche.
- Binární vyhledávání (nebo také metoda půlení intervalu) je vyhledávací algoritmus na nalezení zadané hodnoty v uspořádaném seznamu pomocí zkracování seznamu o polovinu v každém kroku. Binární vyhledávání najde medián, porovná s hledanou hodnotou a na základě výsledku porovnání se rozhodne o pokračování v horní nebo dolní části seznamu a rekurzivně pokračuje od začátku.
- Puolitushaku on tietojenkäsittelytieteessä tehokas ja yleisesti käytetty hakualgoritmi tiedon etsimiseen järjestetystä taulukosta. Puolitushaun ideana on etsiä etsittävää alkiota taulukon keskeltä, ja mikäli alkiota ei löytynyt, voidaan alkion etsimistä jatkaa alkuperäisen taulukon alku- tai loppupään puolivälistä riippuen siitä onko haettava arvo pienempi vai suurempi kuin taulukon keskellä oleva alkio.
- La dichotomie (« couper en deux » en grec) est, en algorithmique, un processus itératif ou récursif de recherche où, à chaque étape, l'espace de recherche est restreint à l'une des deux parties. On suppose bien sûr qu'il existe un test relativement simple permettant à chaque étape de déterminer l'une des deux parties dans laquelle se trouve une solution.
- In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca per individuare un determinato valore all'interno di un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.
- Binærsøk er en effektiv algoritme for å finne fram til et bestemt element i en sortert liste ved å dele listen i to for hvert steg. Algoritmen tar det midterste elementet i den sorterte listen og sammenligner med det elementet en skal finne fram til for å finne ut om det er større eller mindre. Fordi listen er sortert vet en dermed om elementet kommer før eller etter, og søker deretter i den gjenstående halvdelen på samme måte.
- Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks. Np. jeśli tablica zawiera milion elementów, wyszukiwanie binarne musi sprawdzić maksymalnie 20 elementów (<math>\log_2{1\,000\,000} \approx 20</math>) w celu znalezienia żądnej wartości.
- A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso.
- Algoritmul de căutare binară este un algoritm de căutare folosit pentru a găsi un element într-o listă ordonată(tablou unidimensional/vector). Algoritmul funcţionează pe baza tehnicii divide et impera. Valoarea căutată este comparată cu cea a elementului din mijlocul listei. Dacă e egală cu cea a acelui element, algoritmul se termină.
- Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Также применяется для нахождения заданного значения монотонной (невозрастающей или неубывающей) функции.
- Binärsökning är en algoritm för att avgöra om en mängd innehåller ett givet element. Sökningen utförs i flera steg och i varje steg skall man utesluta att halva den kvarvarande mängden innhåller elementet och därmed kunna koncentrera sig på den andra halvan. Intervallhalveringsmetoden är en term som används om både binärsökning och den matematiska problemlösningsmetoden i Bolzanos sats.
- İkili Arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır. Bu teknikteki her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir.
- Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння.
|
![[RDF Data]](/statics/sw-cube.png)
