CODEWITHSUNDEEP
pythonbinary-search
evagoras
evagoras

Reputation: 1

Binary search approach not working for all cases

I'm trying to do a LeetCode question:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

I have attempted to approach the problem using recursion by utilizing the offset difference between the middle indices of each subarray. However, in each instance, there is another case where the code fails. Any thoughts ?

def binary(nums, target, answer):
    n = len(nums)  

    if len(nums) == 1 and nums[0] != target: 
        #special case where the subarray is length one and it doesnt match the target
        return -1 

    if nums[n // 2] == target:
        return answer
    elif nums[n // 2] > target:
        answer = binary(nums[:n // 2], target, answer)
    else:
        answer = binary(nums[n // 2 + 1:], target, answer+(n // 2) + 1)

    return answer

class Solution(object):
    def search(self, nums, target):
        #Adjusting the offset in the beginning
        if nums[0] == target:
            return 0
        elif nums[len(nums) // 2] >= target:
            return binary(nums, target, len(nums) // 2)
        else:
            return binary(nums, target, 0)

Upvotes: 0

Views: 79

Answers (1)

Andrej Podzimek
Andrej Podzimek

Reputation: 2788

There is no need for recursion. The trick is to maintain a lower bound and an upper bound (+ 1) on the remaining range in which the target value may still be. In each iteration, look at the “middle” (median, sort of, albeit not by the statistical meaning) of the range. If its value is above the target, make it the upper bound. If it is below the target, make it the lower bound (+ 1). The last remaining possibility is that you’ve found the target. If the [lower, upper) interval collapses, then the target was not found.

The only surprising bit may be lower = current + 1 versus upper = current, but given that upper has the “one past end” meaning (in the same sense as in e.g. range(lower, upper)), this shouldn’t be surprising after all.

def search(nums, target):
  lower, upper = 0, len(nums)
  while lower < upper:
    current = (lower + upper) // 2
    if nums[current] < target:
      lower = current + 1
    elif nums[current] > target:
      upper = current
    else:
      return current
  return -1

A more interesting task would be to not just find any occurrence of target, but to also figure out the entire index range of nums equal to target — still in logarithmic time. 😀 (A possible approach would be to search for an element equal to target such that the following element is larger than target (or the last element if equal to target), then search for an element equal to target such that the previous element is smaller than target (or the first element if equal to target), then summarize the result.)

Upvotes: 1

Related Questions