def ternarySearch(target, nums, left, right):

  if left > right:
    return -1

  mid1 = left  + (right-left+1) // 3
  mid2 = right - (right-left+1) // 3

  if nums[mid1] == target:
    return mid1

  if nums[mid2] == target:
    return mid2

  if target > nums[mid1]:
    # target must be on the left segment
    return ternarySearch(target,nums,left,mid1-1)

  if target < nums[mid1] and target > nums[mid2]:
    # target must be on the middle segment
    return ternarySearch(target,nums,mid1+1,mid2-1)

  # target must be on the right segment
  return ternarySearch(target,nums,mid2+1,right)

def main():
  nums = [443,339,333,231,202,17,11,9,8,7,6,5,4,1]
  for target in [11,111]:
    print(ternarySearch(target,nums,0,len(nums)-1))  # should print 6 and -1

  nums = [10*i for i in range(100,0,-1)]
  for target in [460,466]:
    print(ternarySearch(target,nums,0,len(nums)-1))  # should print 54 and -1

main()

6
-1
54
-1

def ternarySearch(target, nums, left, right):

  if left > right:
    return -1
  
  if nums[left  + (right-left+1) // 3] == target:
    return left  + (right-left+1) // 3

  if nums[right - (right-left+1) // 3] == target:
    return right - (right-left+1) // 3

  if target > nums[left  + (right-left+1) // 3]:
    # target must be on the left segment
    return ternarySearch(target,nums,left,left  + (right-left+1) // 3 - 1)

  if target < nums[left  + (right-left+1) // 3] and target > nums[right - (right-left+1) // 3]:
    # target must be on the middle segment
    return ternarySearch(target,nums,left  + (right-left+1) // 3 + 1,right - (right-left+1) // 3-1)

  # target must be on the right segment
  return ternarySearch(target,nums,right - (right-left+1) // 3+1,right)