Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957. Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book's entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Interpolační vyhledávání (cs)
- Interpolationssuche (de)
- Interpolation search (it)
- Interpolation search (en)
- Recherche par interpolation (fr)
- Интерполяционный поиск (ru)
- Інтерполяційний алгоритм пошуку (uk)
- 插值搜尋 (zh)
|
| rdfs:comment
| - Die Interpolationssuche, auch Intervallsuche genannt, ist ein von der binären Suche abgeleitetes Suchverfahren, das auf Listen und Feldern zum Einsatz kommt. Während der Algorithmus der binären Suche stets das mittlere Element des Suchraums überprüft, versucht der Algorithmus der Interpolationssuche im Suchraum einen günstigeren Teilungspunkt als die Mitte zu erraten. Die Arbeitsweise ist mit der eines Menschen vergleichbar, der ein Wort in einem Wörterbuch sucht: Die Suche nach Zylinder wird üblicherweise am Ende des Wörterbuches begonnen, während die Suche nach Aal im vorderen Bereich begonnen werden dürfte. (de)
- La recherche par interpolation est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. (fr)
- 插值搜尋法（Interpolation search）是利用插值公式來計算猜測搜尋鍵值的位置。搜尋方式與二分搜尋相同。 插值公式： 插值 = (設算數 - 最小數) / (最大數 - 最小數)： 搜尋鍵值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( right - left ) ) (zh)
- Interpolační vyhledávání je vyhledávací algoritmus pro nalezení zadané hodnoty v uspořádaném seznamu hodnot. Algoritmus je vylepšením binárního vyhledávání pro případy, kdy jsou hodnoty v seznamu nejen seřazené, ale zároveň rovnoměrně rozložené. Tuto metodu intuitivně používají lidé například při vyhledávání ve slovníku – odhadnou, kde by přibližně mohlo hledané heslo být (např. heslo začínající písmenem „K“ bude pravděpodobně někde před polovinou slovníku) a otevřou slovník na odhadnutém místě. Podle odchylky postupují dopředu nebo dozadu o menší nebo větší počet stránek. (cs)
- Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957. Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book's entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or (en)
- L'interpolation search è un algoritmo di ricerca di un dato valore chiave in un array ordinato tramite gli stessi valori delle chiavi. È il metodo corrispondente alla ricerca di un particolare termine all'interno di un dizionario o di un nominativo all'interno di un elenco telefonico. L'interpolation search può essere considerato come una generalizzazione della ricerca dicotomica; quest'ultima, infatti, segue lo stesso procedimento, ma non si basa sui valori degli estremi, bensì taglia il search space sempre a metà. (it)
- Інтерполяційний алгоритм пошуку — алгоритм для пошуку за заданим ключем в індексованому масиві, який впорядкований за значенням ключів. Це схоже до того, як люди шукають певне ім'я в телефонній книзі. На кожному кроці обчислюється, в якому полі пошуку може бути елемент, базуючись на граничних значеннях цього поля і ключі шуканого елемента, зазвичай за допомогою лінійної інтерполяції. Ключ на вибраній позиції порівнюється з шуканим ключем і, якщо вони не рівні, то залежно від результату порівняння, простір пошуку зводиться до частини до або після даного ключа. Цей метод працюватиме тільки в тому випадку, коли порівняння між ключами є розумним. (uk)
- Интерполяционный поиск (интерполирующий поиск) основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий ещё учитывает и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки. В среднем интерполирующий поиск производит log(log(N)) операций, где N есть число элементов, среди (ru)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| space
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| caption
| - Visualization of the interpolation search algorithm in which 24 is the target value. (en)
|
| class
| |
| data
| |
| time
| |
| has abstract
| - Interpolační vyhledávání je vyhledávací algoritmus pro nalezení zadané hodnoty v uspořádaném seznamu hodnot. Algoritmus je vylepšením binárního vyhledávání pro případy, kdy jsou hodnoty v seznamu nejen seřazené, ale zároveň rovnoměrně rozložené. Tuto metodu intuitivně používají lidé například při vyhledávání ve slovníku – odhadnou, kde by přibližně mohlo hledané heslo být (např. heslo začínající písmenem „K“ bude pravděpodobně někde před polovinou slovníku) a otevřou slovník na odhadnutém místě. Podle odchylky postupují dopředu nebo dozadu o menší nebo větší počet stránek. Interpolační vyhledávání se zakládá na myšlence, že u rovnoměrně rozložených hodnot v seznamu můžeme odhadnout umístění a tím snížit počet nutných kroků k nalezení prvku. Jako příklad budeme uvažovat seznam čísel 1, 2, 3 ... až 1000. Pokusíme se najít prvek 125. Pokud bychom hledali pomoci binárního vyhledávání, prvním testovaným prvkem by bylo číslo 500, poté číslo 250 a nakonec námi hledané číslo 125. Interpolační vyhledávací algoritmus odhadne pozici a přímo přejde na prvek 125. Složitost tohoto algoritmu pro rovnoměrně rozložená data je O(log log n). V nejhorším případě ovšem může být složitost až O(n). Aby se zabránilo nejhoršímu případu, je možné kombinovat interpolační vyhledávání s binárním vyhledáváním – například střídat vždy jeden krok interpolačního vyhledávání a jeden binárního vyhledávání. (cs)
- Die Interpolationssuche, auch Intervallsuche genannt, ist ein von der binären Suche abgeleitetes Suchverfahren, das auf Listen und Feldern zum Einsatz kommt. Während der Algorithmus der binären Suche stets das mittlere Element des Suchraums überprüft, versucht der Algorithmus der Interpolationssuche im Suchraum einen günstigeren Teilungspunkt als die Mitte zu erraten. Die Arbeitsweise ist mit der eines Menschen vergleichbar, der ein Wort in einem Wörterbuch sucht: Die Suche nach Zylinder wird üblicherweise am Ende des Wörterbuches begonnen, während die Suche nach Aal im vorderen Bereich begonnen werden dürfte. (de)
- Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957. Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book's entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible. By comparison, binary search always chooses the middle of the remaining search space, discarding one half or the other, depending on the comparison between the key found at the estimated position and the key sought — it does not require numerical values for the keys, just a total order on them. The remaining search space is reduced to the part before or after the estimated position. The linear search uses equality only as it compares elements one-by-one from the start, ignoring any sorting. On average the interpolation search makes about log(log(n)) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons. In interpolation-sequential search, interpolation is used to find an item near the one being searched for, then linear search is used to find the exact item. (en)
- La recherche par interpolation est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. (fr)
- L'interpolation search è un algoritmo di ricerca di un dato valore chiave in un array ordinato tramite gli stessi valori delle chiavi. È il metodo corrispondente alla ricerca di un particolare termine all'interno di un dizionario o di un nominativo all'interno di un elenco telefonico. Ad ogni passo della ricerca, l'algoritmo valuta dove può trovarsi l'elemento all'interno del search space basandosi sui valori delle chiavi agli estremi dell'array e sul valore da cercare. Dopodiché confronta la chiave selezionata con il valore da cercare. Se si tratta del valore richiesto, allora l'algoritmo è terminato. Altrimenti il search space viene sostituito con la parte restante destra o sinistra dell'array, a seconda del risultato del confronto. L'interpolation search può essere considerato come una generalizzazione della ricerca dicotomica; quest'ultima, infatti, segue lo stesso procedimento, ma non si basa sui valori degli estremi, bensì taglia il search space sempre a metà. In media, il costo dell'algoritmo è di log(log(n)) confronti (dove n è la dimensione dell'array), ma è efficace solo se le chiavi sono distribuite in maniera ragionevolmente uniforme, ovvero se la differenza fra due valori contigui è pressoché costante. Nel caso peggiore (ad esempio, se il valore numerico delle chiavi aumenta esponenzialmente), si avranno O(n) confronti. (it)
- Интерполяционный поиск (интерполирующий поиск) основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий ещё учитывает и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки. В среднем интерполирующий поиск производит log(log(N)) операций, где N есть число элементов, среди которых производится поиск. Число необходимых операций зависит от равномерности распределения значений среди элементов. В плохом случае (например, когда значения элементов экспоненциально возрастают) интерполяционный поиск может потребовать до O(N) операций. (ru)
- Інтерполяційний алгоритм пошуку — алгоритм для пошуку за заданим ключем в індексованому масиві, який впорядкований за значенням ключів. Це схоже до того, як люди шукають певне ім'я в телефонній книзі. На кожному кроці обчислюється, в якому полі пошуку може бути елемент, базуючись на граничних значеннях цього поля і ключі шуканого елемента, зазвичай за допомогою лінійної інтерполяції. Ключ на вибраній позиції порівнюється з шуканим ключем і, якщо вони не рівні, то залежно від результату порівняння, простір пошуку зводиться до частини до або після даного ключа. Цей метод працюватиме тільки в тому випадку, коли порівняння між ключами є розумним. До прикладу, двійковий пошук завжди вибирає середину в даному полі пошуку і відкидає одну з половин, порівнюючи значення середини з шуканим. А лінійний пошук порівнює всі елементи один за одним, ігноруючи впорядкованість. В середньому інтерполяційний пошук робить log(log(n)) порівнянь(якщо елементи є рівномірно розприділеними), де n- кількість елементів. В найгіршому випадку їх кількість може виростати до O(n). (uk)
- 插值搜尋法（Interpolation search）是利用插值公式來計算猜測搜尋鍵值的位置。搜尋方式與二分搜尋相同。 插值公式： 插值 = (設算數 - 最小數) / (最大數 - 最小數)： 搜尋鍵值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( right - left ) ) (zh)
|
| average-time
| |
| best-time
| |
| optimal
| |
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is differentFrom
of | |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
