Draft:Bogo Search
Submission declined on 9 September 2024 by KylieTastic (talk). This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources. This draft's references do not show that the subject qualifies for a Wikipedia article. In summary, the draft needs multiple published sources that are:
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|
Introduction
[edit]Class | Search |
---|---|
Data structure | Array |
Worst-case performance | O(∞) |
Worst-case space complexity | O(1) for unchecked |
In Computer science, bogosearch (also known as random search and stupid search), is a Search algorithm based on the Generate and test paradigm. The function successively generates a random index of its input until it finds one that matches the target. It is not considered useful for searching, but may be used for educational purposes, to contrast with more efficient algorithms.
Two versions of the algorithm exists: a joke one that only stop when it finds its target (indefinitely) and one that tries random numbers while keep tracking of tries. The algorithm's name is a portmanteau of the words bogus and search.
Description of the Algorithm
[edit]Pseudocode
[edit]The following is a description of the unchecked one in pseudocode:
algorithm bogosearch(list, target) is while True do n = random(0..list.length) if list[n] equals to target then return n
The following is a descriptions with the check in pseudocode:
algorithm bogosearch(list, target) is ntries = 0 arr = [] while True do if n tries equals to list.length then return -1 else n = random(0..list.length) if bogosearch(arr, n) equals to -1 then ntries++ arr.append(n) if list[n] equals to target then return n else continue
Python
[edit]Implementation of both uses in python:
import random
def bogo_search(list, k):
"""
:type list: list
:type k: var
:rtype: int
"""
while True:
index = random.randint(0, len(list) - 1)
print(index)
if list[index] == k:
return index
def bogo_search(list, k):
"""
:type list: list
:type k: var
:rtype: int
"""
ntries = 0
arr = []
while True:
if ntries == len(list):
print("not found")
return None
else:
index = random.randint(0, len(list) - 1)
print(index)
if bogo_search(arr, index):
ntries += 1
arr.append(index)
if list[index] == k:
return index
else:
continue
Complexity Study and Cases
[edit]This is a work in progress, not finished yet.