By accident Again

using programming by accient we solved Search in Rotated Sorted Array.

But, this time, We can t sure the target number is on the left or on the right of the mid.

e.g.

t = 2

[ 1 1 1 1 1 1 2 1 1 1 1]
  s         m         e    

this time, we do not know s = m + 1 or e = m.

Brute force again

s m e may be like below. (put == or != between s m e)

  • s != m != e
  • s != m == e
  • s == m != e
  • s == m == e

s != m != e

this is handled by Search in Rotated Sorted Array.

s != m == e

[ 1 1 1 1 2 2 2 2 2 2 2]
  s         m         e    

m == e means m .. e are the same number. they are safe to be removed. Remember, number at m does not equal to t, because we had checked if A[m] == t before.

s == m != e

[ 1 1 1 1 1 1 1 2 2 2 2]
  s         m         e    

this case is the same as s != m == e

s == m == e

Wrost case

t = 2

[ 1 1 1 1 1 1 2 1 1 1 1]
  s         m         e    

we only know t does not equal to s m or e.

what we can do it only search again by doing

s = s + 1
e = e - 1