| p:abstract
| - A binary search algorithm' (or binary chop) is a technique for locating a particular value in a sorted list of values. To cast this in the frame of the guessing game, realize that we seek to guess the index, or numbered place, of the value in the list. The method makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span, comparing its value to the target value, and determining if the selected value is greater than, less than, or equal to the target value. A guessed index whose value turns out to be too high becomes the new upper bound of the span, and if its value is too low that index becomes the new lower bound. Only the sign of the difference is inspected: there is no attempt at an interpolation search based on the size of the difference. Pursuing this strategy iteratively, the method reduces the search span by a factor of two each time, and soon finds the target value or else determines that it is not in the list at all. A binary search is an example of a dichotomic divide and conquer search algorithm. Finding the index of a specific value in a sorted list is useful because, given the index, other data structures will contain associated information. Suppose a data structure containing the classic collection of name, address, telephone number and so forth has been accumulated, and an array is prepared containing the names, numbered from one to N. A query might be: what is the telephone number for a given name X. To answer this the array would be searched and the index corresponding to that name determined, whereupon the associated telephone number array would have Xs telephone number at that index, and likewise the address array and so forth. Appropriate provision must be made for the name not being in the list (typically by returning an index value of zero), indeed the question of interest might be only whether X is in the list or not.If the list of names is in sorted order, a binary search will find a given name with far fewer probes than the simple procedure of probing each name in the list, one after the other in a linear search, and the procedure is much simpler than organizing a hash table. However, once created, searching with a hash table may well be faster, typically averaging just over one probe per lookup. With a non-uniform distribution of values, if it is known that some few items are much more likely to be sought for than the majority, then a linear search with the list ordered so that the most popular items are first may do better than binary search. The choice of the best method may not be immediately obvious. If, between searches, items in the list are modified or items are added or removed, maintaining the required organisation may consume more time than the searches. (en)
- En algorithmique, la dichotomie (« couper en deux » en grec) est 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 », 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 de recherche, et à chaque étape, on coupera l'espace de recherche en deux parties de même taille 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. (fr)
- 二分探索（にぶんたんさく、BS;Binary Search）とは検索のアルゴリズムの一つ。二分検索、バイナリサーチともいう。 ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。 大小関係を用いるため、未ソートのリストや配列には二分探索を用いることはできない。 n個のデータがある場合、時間計算量は<math>O(\log_2 n)</math>である（O記法）。 n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。 (ja)
- 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. (pl)
- Двоичный (бинарный) поиск — алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании. (ru)
- La búsqueda binaria o búsqueda dicotómica es un algoritmo de búsqueda. Para realizarla, es necesario contar con un array o vector ordenado. Luego tomamos un elemento central, normalmente el elemento que se encuentra a la mitad del arreglo, y lo comparamos con el elemento buscado. Si el elemento buscado es menor, tomamos el intervalo que va desde el elemento central al principio, en caso contrario, tomamos el intervalo que va desde el elemento central hasta el final del intervalo. Procedemos de esta manera con intervalos cada vez menores hasta que lleguemos a un intervalo indivisible, en cuyo caso el elemento no está en el vector, o el elemento central sea nuestro elemento.De esta forma la complejidad computacional se reduce a O(log N).El algoritmo se puede implementar con o sin recursión, a continuación se presenta una versión iterativa en Lenguaje C: int Bbin{ int inicio, final, medio; inicio = 0; final = n - 1; while { medio = / 2; if return; else if inicio = medio + 1; else final = medio - 1; } return -1; }Aquí se muestra una versión recursiva del mismo algoritmo: int bbin { int medio = floor; if return -1; if return medio; else if return bbin; else if return bbin; }Categoría:Algoritmos de búsqueda (es)
- 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, 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 while vasen ≤ oikea keski ← /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 eli algoritmi vaatii vain vakiomäärän muistia. Käytännössä moni ohjelmoija tekee virheen kirjoittaessaan / 2, sillä useimmissa ohjelmointikielissä kokonaislukuarvo vasen + oikea voi pyörähtää tällöin ympäri. Oikea ratkaisu on kirjoittaa esimerkiksi vasen + (/ 2). (fi)
- 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. (it)
- 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. (pt)
- 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. (de)
- 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 if right < left return not found mid := floor if value > a[mid] return binarySearch else if value < a[mid] return binarySearch(a, value, left, mid-1) else return mid (no)
|
| rdfs:comment
| - A binary search algorithm' (or binary chop) is a technique for locating a particular value in a sorted list of values. To cast this in the frame of the guessing game, realize that we seek to guess the index, or numbered place, of the value in the list. The method makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span, comparing its value to the target value, and determining if the selected value is greater than, less than, or equal to the target value. A guessed index whose value turns out to be too high becomes the new upper bound of the span, and if its value is too low that index becomes the new lower bound. Only the sign of the difference is inspected: there is no attempt at an interpolation search based on the size of the difference. Pursuing this strategy iteratively, the method reduces the search span by a factor of two each time, and soon finds the target value or else determines that it is not in the list at all. A binary search is an example of a dichotomic divide and conquer search algorithm. (en)
- En algorithmique, la dichotomie (« couper en deux » en grec) est un processus itératif ou récursif de recherche où, � chaque étape, l'espace de recherche est restreint � l'une des deux parties. (fr)
- 二分探索（にぶんたんさく、BS;Binary Search）とは検索のアルゴリズ� の一つ。二分検索、バイナリサーチともいう。 ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。 大小関係を用いるため、未ソートのリストや配列には二分探索を用いることはできない。 n個のデータがある� �合、時間計算量は<math>O(\log_2 n)</math>である（O記法）。 n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の� �合は/2個、偶数の� �合はn/2個または(n/2)-1個）の要� を無視することができる。 (ja)
- 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. (pl)
- Двоичный (бинарный) поиск — алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. (ru)
- La búsqueda binaria o búsqueda dicotómica es un algoritmo de búsqueda. Para realizarla, es necesario contar con un array o vector ordenado. Luego tomamos un elemento central, normalmente el elemento que se encuentra a la mitad del arreglo, y lo comparamos con el elemento buscado. (es)
- Puolitushaku on tietojenkäsittelytieteessä tehokas ja yleisesti käytetty hakualgoritmi tiedon etsimiseen järjestetystä taulukosta. (fi)
- 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. (it)
- 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. (pt)
- 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. (de)
- 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. (no)
|
![[RDF Data]](http://dbpedia.org/statics/sw-cube.png)
