I'm new to algorithm in programming and got this problem of implementing the binary search for an unsorted list in python. I figured out how to implement the recursive binary search function below but got into some troubles with recursion depth limit. So I'm curios whether there is another way to implement binary search for unsorted list in python or not:

def binary_search_unsorted(unsortedList, target):
    if len(unsortedList) == 0:
        return False;
    else:
        start = unsortedList[0];
        if start == target:
            return True;
        else:
            if start < target:
                return binary_search_unsorted([n for n in unsortedList if n > start], target);
            else:
                return binary_search_unsorted([n for n in unsortedList if n < start], target);

CodePudding user response：

Binary search for an unsorted data structure of any kind is futile and makes not sense, regardless of how it is implemented.

Binary search relies on the premise that it can rule out large parts of the search space by just looking at the current value and comparing it with the target value, because it can make assumptions about those elements since the data structure is sorted.

Think about the problem you are trying to solve again and ask the source who has provided it some serious questions.

CodePudding user response：

Since you are only using tail-recursion (that is, you never do anything with a recursive call other than return its result), this can be re-written as a loop w/o recursion in a very straight-forward manner.