```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

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

#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

return None
return current

def contains(self, value):
if self.root == None:
return False
current = self.root
found = False

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)

```
star

Fri Aug 12 2022 22:53:09 GMT+0000 (UTC) https://leetcode.com/problems/search-in-rotated-sorted-array/submissions/

#python #binary #search #leetcode #neetcode