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 ﬁrst 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 ﬁrst 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 eﬃciency 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
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
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
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