Python: Binary Search - "Find the first occurrence"

having a bit of trouble with this one. I have included what I have below. When I submit it, it keeps saying "Program timed out" for some reason. I am not sure what to do next. It works to a certain degree, ie, some tests work, not the last test just doesn't work. What do you suggest?

I have included a screenshot of the question, as well as what I have so far.

Here is the note (pseudocode) from class, I just need to modify this to modify it to print the first occurance of the target in the ordered_list. If the target does not exist in the list, it must return None.

Thank you in advance!!

The Question: You are to write the code of a Python function

binsearch first(ordered list, target)

that, given a nonempty ordered list of items and a target item, all of the same type, returns the index of the first occurrence of the target in the list, if the target is in the list, and None otherwise.

For example, the call binsearch first([1, 3, 3, 7, 9], 3) should return 1 since the first 3 is at index 1. Similarly, the call binsearch first([1, 3, 3, 7, 9], 9) should return 4, and the call binsearch first([1, 3, 3, 7, 9], 5) should return None.

You may not assume anything about the type of the items, other than that they are orderable. For example, items could be strings and the call binsearch first(["Alice", "Bob", "Chloe", "Chloe", "Dave"], "Chloe") should return 2.

Your program will be evaluated for efficiency and style. For full credit, it may only make a single test for equality (it may only have a single “==” comparison which, additionally, may not be within any loop). That is, the only equality test happens at the end of execution, just before returning.

Restrictions: Recursion is not allowed for this problem. allowed to use any operations other than

Furthermore, you are not

  • , − , // , × , < ,

and (once) ==

Of course, all builtins and library functions related to search are also disallowed: you have to do the coding yourself.

def binsearch_first(ordered_list, target):
    left = 0
    right = len(ordered_list) - 1
    count = 0
    while left <= right:
        mid = (left + right) // 2
        count = count + 1
        if ordered_list[mid] == target:
            while mid > 0 and ordered_list[mid - 1] == target:
                mid = mid - 1
            return mid
        elif target < ordered_list[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return None

Find the first occurrence

2 answers

  • answered 2019-12-13 04:23 Solen'ya

    I am not a CS student hence cannot comment on the effectiveness of the program, but you can achieve your goal by using a simple for loop

    def binsearch_first(ordered_list, target):
        i=0
        for ele in ordered_list:
            if ele == target:
                return i 
                break
            else:
                i+=1
        return None 
    

    Result of this is:

    >>> binsearch_first([1, 3, 3, 7, 9], 3)
    1
    >>> binsearch_first(["Alice", "Bob", "Chloe", "Chloe", "Dave"], "Chloe")
    2
    

    Regards

  • answered 2019-12-13 06:36 wontleave

    The only operator that works with string and integer is <. We have to make use of the fact that it is an ordered list - arranged in increasing order.

    def binsearch(orderedlist,target):
      candidate = 0
      for i in range(len(orderedlist)):
        if orderedlist[i] < target:
          candidate = candidate
        else:
          if i+1 < len(orderedlist):
            if orderedlist[i] < orderedlist[i+1]:
              #it is an ordered list so if i+1 is not bigger than i, it must be equal
              candidate = candidate
            else:
              candidate = i
              break # can you use break?
      if orderedlist[candidate] == target:
        return candidate
      else:
        return None