class Solution:
    def binarySearch(self, nums, target):
        start, end = 0, len(nums) - 1 

        while start <= end: 
            middle = (start + end) // 2 
            current = nums[middle] 

            if target > current: 
                start = middle + 1 
            elif target < current: 
                end = middle - 1 
            else: 
                return middle
                #return current if you want value instead of index 
        return -1 
    
    
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0: 
            return -1 
        elif len(nums) == 1: 
            if nums[0] != target: 
                return -1 
            else: 
                return 0 
        else: 
            rotated = False
            lastIdx = len(nums) - 1 

            if nums[lastIdx] < nums[0]: 
                rotated = True 

            if rotated == False: 
                return self.binarySearch(nums, target) 
            else: 
                previous = nums[0]
                rotateIdx = 0 
                for i in range(1, len(nums)): 
                    if nums[i] < previous: 
                        rotateIdx = i 
                    previous = nums[i]
                    
                array1 = nums[:rotateIdx]
                array1Length = len(array1)
                array2 = nums[rotateIdx:] 

                if self.binarySearch(array1, target) == -1 and self.binarySearch(array2, target) != -1: 
                    return array1Length + self.binarySearch(array2, target)
                return self.binarySearch(array1, target)

# //Lists are linear but trees are nonlinear 
# //Often working with binary trees and specifically binary search trees 
 
# //SL is techically a special case tree 
 
# //Root: top node of tree
# //Child: node directly connected to another node when moving away from root 
# //Parent: converse notion of child 
# //Siblings: group of node with same parent 
# //Leaf: node with no children 
# //Edge: connection betweeen one node and another (often arrows) 
 
# //Used for HTML DOM, network routing, abstract syntax trees, folder organization, AI, best possible move (decision tree)
 
# //We will focus on binary search tree (can only have at most 2 child nodes)
# //For each node, everything to left is smaller. Right >> bigger
 


class Node: 
  def __init__(self, value): 
    self.value = value 
    self.left = None 
    self.right = None 

class BinarySearchTree: 
  def __init__(self): 
    self.root = None 

  #adds number to correct place 
  def insert(self, value): 
    #creates new Node   
    new_node = Node(value) 
    #start at root 
    #if no root exists, root becomes new_node 
    if self.root == None: 
      self.root = new_node 
      return self 
    
    current = self.root 
    
    while True: 
      #to handle special case where value is same as current node 
      #you can return None or you can add a counter property 
      if value == current.value: 
        return None 
      #check to see if value is less than current 
      if value < current.value: 
        #check to see if there is node to left 
        #if not, add new_node to left 
        if current.left == None: 
          current.left = new_node 
          return self
        #if there is node to left, move to that node and repeat 
        current = current.left 
      #check to see if value is greater than current 
      else: 
        #check to see if there is node to right 
        #if not, add new_node to right 
        if current.right == None: 
          current.right = new_node 
          return self 
        #if there is node to right, move to that node and repeat 
        current = current.right 
  
  #find() returns value while contains() returns boolean 
  #find will point to entire node 
  def find(self, value): 
    #check to see if there is root and if not, we are done! 
    if self.root == None: 
      return False 
    current = self.root 
    found = False 
    
    while current and not found: 
      #if value is less than current 
      if value < current.value: 
        #check to see if there is node to left 
        #if there is, move to that node and repeat 
        current = current.left 
        #if not, we ar edone because current will no longer exist 
      #if value is greater than current 
      elif value > current.value: 
        #check to see if there is node to right 
        #if there is, move to that node and repeat 
        current = current.right 
        #if not, we are done because current will no longer exist 
      else: 
        found = True 
    
    if not found:
      return None 
    return current 
    
  def contains(self, value): 
    if self.root == None: 
      return False 
    current = self.root 
    found = False 
    
    while current and not found: 
      if value < current.value: 
        current = current.left 
      elif value > current.value: 
        current = current.right 
      else: 
        return True 
    return False 
          
t = BinarySearchTree()
t.insert(3)
t.insert(5)
t.insert(2)
t.insert(-1)
t.insert(6)
t.find(6) 
t.contains(6)

# // Insertion and Search: O(log N) VERY GOOD 
# // Not guaranteed if BST is a one sided tree (choose a different root) 
 
 
 
# //      10
# //   5     13
# // 2  7  11  16
 
# // tree = BinarySearchTree()
# // tree.insert(10)
# // tree.insert(5)
# // tree.insert(13)
# // tree.insert(11)
# // tree.insert(2)
# // tree.insert(16)
# // tree.insert(7)
# // tree.find(7) >> will point to node with 7  
# // tree.contains(6) >> False 
 
 
 
 
 
# //Primitive way of making Tree before insert() 
# // tree = BinarySearchTree()
# // tree.root = Node(10)
# // tree.root.right = Node(15)
# // tree.root.left = Node(7)
# // tree.root.left.right = Node(9)