You must write an algorithm with O(log n) runtime complexity? What does this mean? So the question was "Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order"
Here is my code:
if target in nums:
print(nums.index(target))
else:
nums.append(target)
nums.sort()
print(nums.index(target))
If you search for something in n things, starting at the beginning, in the worst case you will check all n things. This would be O(n).
If the things are sorted, you can get away with checking the middle value then looking to the first half or second half, or rather checking the middle of the appropriate half, and keep halving, thereby only checking up to log2(n), giving a O(log n) worst case.
Look at python's bisect - though note the docs point out the insort method is O(n) because of the insert.... you are doing an insert but the question only seems to want to know the index.
