0

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);
  • 5
    *"got this problem of implementing the binary search for an unsorted list"* - Whoever gave you that problem is trolling you. – Kelly Bundy Feb 02 '22 at 13:06
  • 2
    The binary search algorithm supposes the list is sorted. You can't binary search an unsorted list. See: https://stackoverflow.com/questions/35895627/can-we-use-binary-search-with-an-unsorted-array/35895909 – kabooya Feb 02 '22 at 13:07
  • Would this help? https://stackoverflow.com/questions/33713643/binary-search-of-an-unsorted-list – kapebm Feb 02 '22 at 13:09
  • Your search is not binary since it does not split the list in half at each step. It is a slow linear search. – stark Feb 02 '22 at 13:56
  • @stark If it's a *linear* search, why does it take up to *quadratic* time? – Kelly Bundy Feb 02 '22 at 13:59
  • @stark: "binary" doesn't mean "in half", it means "in 2" (although the most effective way to split something in 2 would be in half). – Scott Hunter Feb 02 '22 at 15:50
  • @Scott Hunter I had considered that point as well and checked [Wikipedia](https://en.m.wikipedia.org/wiki/Binary_search_algorithm), which as far as I saw only kept saying half. Can you show a source defining it your way? – Kelly Bundy Feb 02 '22 at 16:00
  • @stark: I wasn't commenting on the meaning of "Binary Search"; I was commenting on the use of the adjective "binary" ("your search is not binary" as opposed to "it isn't a Binary Search"). – Scott Hunter Feb 02 '22 at 16:07

2 Answers2

1

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.

user1984
  • 5,990
  • 2
  • 13
  • 32
-2

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.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101