Binary Search written in python with O(n) [closed]

Question

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
        if nums[i] == None:
          return -1

I think this code will be good for most cases in binary search but in some cases might need a better version of the code that is O(log n).

Answer 1

It's not really a binary search if it is not O(log(n)).

Binary search only works on sorted inputs and it takes advantage of the fact that it is sorted to achieve logarithmic complexity.

So it's quite the opposite - your version will be significantly inefficient for almost all programs that could use true binary search instead.

See, for example, here how to implement binary search in python

Answer 2

search([2, None, 3], 3) will return -1, and I think users will find this unexpected. That is, the function doesn't just search, it has an added effect of returning -1 when it finds a None value.

The recommended way to check if a value is None is using the is keyword: if value is None:

When using both the index and the item during an iteration, the enumerate function is practical.

def search(nums, target):
    for index, num in enumerate(nums):
        if num == target:
            return index
       
    return -1