Draft: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 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

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 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

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.