Jump to content

Draft:Bogo Search

From Wikipedia, the free encyclopedia

Introduction

[edit]
Bogo Search
ClassSearch
Data structureArray
Worst-case performanceO(∞)
Worst-case space complexityO(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.

References

[edit]