For an array, I'm using a left pointer (pointing to 0) and a right pointer (pointing to end).

For every iteration, if my search element is not found, I increment left and decrement right. This iteration continues until left <= right. Find the code snippet below

left = 0
right = length - 1

while left <= right:
    // search logic
    left += 1
    right -= 1

What will be worst the time complexity of this algorithm?

Also, is this a type of linear search?

  • $\begingroup$ what is the cost of "search logic"? $\endgroup$
    – tstanisl
    Apr 27 at 21:12

$O(n)$, since you still will go through the entire array.

And yes, this is a linear search since $O(n)$ is linear.

  • $\begingroup$ The loop will run only n/2 times right? So wondering if this will be O(n) still. $\endgroup$
    – Shylajhaa
    Apr 27 at 19:01
  • 2
    $\begingroup$ of course, constants do not make a difference in $O$ notation $\endgroup$
    – nir shahar
    Apr 27 at 19:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.