Revision as of 15:13, 23 March 2014

This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template.

Exponential Search

In computer science, an exponential search is an algorithm 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 n) where n 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.

Algorithm

Searching a sorted collection is a common task. However, many algorithms, such as binary search, are made for searching bounded collections. Exponential search allows allows for searching through a sorted, unbounded list for a specified input value (the search "key"). For exponential search, as with binary search, the list should be arranged in ascending or descending order. Exponential search doubles successive guesses to provide an upper bound for a range in which to perform a binary search (i.e., the current index is determined by calculating the next power of 2). In each step, the algorithm compares the search key value with the key value at the current search index. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the element at the current index is smaller than the search key (if the list is sorted in ascending order), the algorithm repeats and skips to the next index by calculating the next power of 2. If the element at the current index is larger than the search key (if the list is sorted in ascending order), an upper bound for the binary search has been found. The search now knows that the search key, if it is contained in the list at all, is located in the interval formed by the previous search index (i.e., the previous power of 2) and the current search index (i.e., the current power of 2). The algorithm then performs a binary search on this interval and returns the result. The result will either be a failure, if the search key is not in the list, or the position of the search key in the list.

Performance

Alternatives

@@ Line 6: / Line 6: @@
 ==Algorithm==
-Searching a sorted collection is a common task. However, many algorithms, such as [[binary search]], are made for searching bounded collections. Exponential search allows allows for searching through a sorted, unbounded list for a specified input value (the search "key"). For exponential search, as with binary search, the list should be arranged in ascending or descending order. Exponential search doubles successive guesses to provide an upper bound for a range in which to perform a binary search (i.e., the current index is determined by calculating the next power (link) of 2). In each step, the algorithm compares the search key value with the key value at the current search index. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the element at the current index is smaller than the search key (if the list is sorted in ascending order), the algorithm repeats and skips to the next index by calculating the next power of 2. If the element at the current index is larger than the search key (if the list is sorted in ascending order), an upper bound for the binary search has been found. The search now knows that the search key, if it is contained in the list at all, is located in the interval formed by the previous search index (i.e., the previous power of 2) and the current search index (i.e., the current power of 2). The algorithm then performs a binary search on this interval and returns the result. The result will either be a failure, if the search key is not in the list, or the position of the search key in the list.
+Searching a sorted collection is a common task. However, many algorithms, such as [[binary search]], are made for searching bounded collections. Exponential search allows allows for searching through a sorted, unbounded list for a specified input value (the search "key"). For exponential search, as with binary search, the list should be arranged in ascending or descending order. Exponential search doubles successive guesses to provide an upper bound for a range in which to perform a binary search (i.e., the current index is determined by calculating the next [[exponentiation|power]] of 2). In each step, the algorithm compares the search key value with the key value at the current search index. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the element at the current index is smaller than the search key (if the list is sorted in ascending order), the algorithm repeats and skips to the next index by calculating the next power of 2. If the element at the current index is larger than the search key (if the list is sorted in ascending order), an upper bound for the binary search has been found. The search now knows that the search key, if it is contained in the list at all, is located in the interval formed by the previous search index (i.e., the previous power of 2) and the current search index (i.e., the current power of 2). The algorithm then performs a binary search on this interval and returns the result. The result will either be a failure, if the search key is not in the list, or the position of the search key in the list.
 ==Performance==