Hi , I am new to Data Structure and trying to get some clarifications.

Following shows an example Logarithmic Time — O(log n) in Python.

def binary_search(data, value):
    n = len(data)
    left = 0
    right = n - 1
    while left <= right:
        middle = (left + right) // 2 # How can make this by 3 to make the search faster
        if value < data[middle]:
            right = middle - 1
        elif value > data[middle]:
            left = middle + 1
            return middle
    raise ValueError('Value is not in the list')
if __name__ == '__main__':
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(binary_search(data, 8))

Can you please explain and write the code on how can make this faster? Maybe for n/3


  • $\begingroup$ You can eliminate "elif" part, if your task mean this under "make this by 3". $\endgroup$ – zkutch Sep 25 at 18:24
  • $\begingroup$ Is that an answer or comment. Because i Ma not following you @zkutch $\endgroup$ – jimcoderush Sep 25 at 20:13
  • $\begingroup$ It's written in place of comment, but if/when you find it interesting I can write also as answer. We need only little more precision what you mean under words "make this by 3". $\endgroup$ – zkutch Sep 25 at 22:14
  • $\begingroup$ @zkutch This code represents finish running the code in n/2 (by looking into the middle value). I am trying to figure out if the elements accessed can be any faster maybe by n/3? $\endgroup$ – jimcoderush Sep 25 at 22:29
  • $\begingroup$ It is famous and well known piece of code for binary search and finish running in worst case for sorted array for $O(\log n)$, not for $n/2$. It looks for middle element and can be rearrange for looking 3 or more sectioning. Why 2 is preferable look at stackoverflow.com/questions/58033873/…. I suggested take of "elif" as extra comparison in code. $\endgroup$ – zkutch Sep 26 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.