Bogo Search

Introduction

Bogo Search

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 exist: a joke one that only stops when it finds its target (indefinitely) and one that tries random numbers while keeping track of tries. The algorithm's name is a portmanteau of the words bogus and search.

Description of the Algorithm

Pseudocode

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 description with the check in pseudocode:

algorithm bogosearch(list, target) is
    ntries = 0
    arr = []
    while True do
        if ntries 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

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

This is a work in progress, not finished yet.

References

This article "Bogo Search" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Bogo Search. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---