An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list.

Property Value
dbo:abstract
  • In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list. Exponential search can also be used to search in bounded lists. Exponential search can even out-perform more traditional searches for bounded lists, such as binary search, when the element being searched for is near the beginning of the array. This is because exponential search will run in O(log i) time, where i is the index of the element being searched for in the list, whereas binary search would run in O(log n) time, where n is the number of elements in the list. (en)
  • En Ciencias de la Computación, una búsqueda exponencial (también llamado búsqueda galopante o búsqueda Struzik)​ es un algoritmo, creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para buscar en listas infinitas/no acotadas ordenadas.​ Hay numerosas maneras para implementarlo siendo la más común determinar el rango en que la llave de búsqueda reside y realizar una búsqueda binaria dentro de dicho rango. Esto demora O(log i) dónde i es la posición de la llave de búsqueda en la lista, si la llave de búsqueda está en la lista, o la posición donde la llave de búsqueda debería estar, si la llave de búsqueda no está en la lista. La búsqueda exponencial también puede ser usada en listas acotadas. La búsqueda exponencial puede incluso mejorar los tiempos de algoritmos de búsqueda en listas acotadas, como búsqueda binaria, cuando el elemento buscado está cerca del principio del array. Esto es porque la búsqueda exponencial correrá en O(log i), donde i es el índice del elemento buscado en la lista, mientras que la búsqueda binaria correría en O(log n), donde n es el número de elementos en la lista. (es)
  • Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik) é um algoritmo, criado por Jon Bentley e Andrew Chi-Chih Yao em 1976, para a busca listas ordenadas ilimitadas. Existem várias maneiras de se implementar este algoritmo, sendo a mais comum determinar um intervalo em que a chave de pesquisa reside e realizar uma busca binária dentro desse intervalo. Isso leva a uma complexidade O(log i), onde i é a posição da chave de pesquisa na lista, se a chave de pesquisa está na lista, ou a posição onde a chave de pesquisa deve estar, caso a chave de pesquisa não está na lista. A busca exponencial também pode ser usada para pesquisar em listas limitadas. A busca exponencial pode ainda ser mais rápido que os métodos de busca tradicionais, tais como busca binária, quando o elemento a ser procurado é próximo ao início da lista. A razão para isso é que a busca exponencial será executada em O(log i), onde i é o índice do elemento que está sendo procurado na lista, enquanto que a busca binária tem complexidade de O(log n), onde n é o número de elementos na lista. (pt)
dbo:wikiPageID
  • 42285695 (xsd:integer)
dbo:wikiPageLength
  • 9442 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1053423450 (xsd:integer)
dbo:wikiPageWikiLink
dbp:averageTime
dbp:bestTime
dbp:class
dbp:data
dbp:optimal
  • Yes (en)
dbp:space
dbp:time
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list. (en)
  • En Ciencias de la Computación, una búsqueda exponencial (también llamado búsqueda galopante o búsqueda Struzik)​ es un algoritmo, creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para buscar en listas infinitas/no acotadas ordenadas.​ Hay numerosas maneras para implementarlo siendo la más común determinar el rango en que la llave de búsqueda reside y realizar una búsqueda binaria dentro de dicho rango. Esto demora O(log i) dónde i es la posición de la llave de búsqueda en la lista, si la llave de búsqueda está en la lista, o la posición donde la llave de búsqueda debería estar, si la llave de búsqueda no está en la lista. (es)
  • Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik) é um algoritmo, criado por Jon Bentley e Andrew Chi-Chih Yao em 1976, para a busca listas ordenadas ilimitadas. Existem várias maneiras de se implementar este algoritmo, sendo a mais comum determinar um intervalo em que a chave de pesquisa reside e realizar uma busca binária dentro desse intervalo. Isso leva a uma complexidade O(log i), onde i é a posição da chave de pesquisa na lista, se a chave de pesquisa está na lista, ou a posição onde a chave de pesquisa deve estar, caso a chave de pesquisa não está na lista. (pt)
rdfs:label
  • Búsqueda exponencial (es)
  • Exponential search (en)
  • Busca exponencial (pt)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License