interview_binarysearch

1.search range

 1 class Solution(object):
 2     def searchRange(self, nums, target):
 3         res=[-1,-1]
 4         if(len(nums)==0):
 5             return res
 6         
 7         left,right=0,len(nums)-1
 8         while(left+1<right):
 9             mid=left+(right-left)//2
　　　　　　　　  #mid=left+((right-left)>>1)
10             if(nums[mid]==target):
11                 right=mid
12             elif(nums[mid]<target):
13                 left=mid+1
14             else:
15                 right=mid-1
16         if(nums[left]==target):
17             res[0]=left
18         elif(nums[right]==target):
19             res[0]=right
20 
21 
22         left,right=0,len(nums)-1
23         while(left+1<right):
24             mid=left+(right-left)//2
25 
26             if(nums[mid]==target):
27                 left=mid
28             elif(nums[mid]<target):
29                 left=mid+1
30             else:
31                 right=mid-1
32         if(nums[right]==target):
33             res[1]=right
34         elif(nums[left]==target):
35             res[1]=left
36 
37         return res

2.search in a rotated array(may have duplicated elements)

 1 class Solution:
 2     def searchInRotate(self,nums,target):
 3         if(len(nums)==0):
 4             return -1
 5 
 6         left,right=0,len(nums)-1
 7 
 8         while(left+1<right):
 9             mid=left+(right-left)//2
10             if(nums[mid]==target):
11                 return mid
12 
13             if(nums[mid]<nums[right]):
14                 if(nums[mid]<=target<=nums[right]):
15                     left=mid
16                 else:
17                     right=mid
18             elif(nums[mid]>nums[right]):
19                 if(nums[left]<=target<=nums[mid]):
20                     right=mid
21                 else:
22                     left=mid
23             else:
24                 right-=1
25 
26         if(nums[left]==target):
27             return left
28         if(nums[right]==target):
29             return right
30         return -1
31 
32 nums1=[9,12,15,20,1,3,6,7]
33 print(Solution().searchInRotate(nums1,15))
34 print(Solution().searchInRotate(nums1,5))
35 
36 
37 
38 nums1=[9,12,15,20,1,1,1,3,6,7]
39 print(Solution().searchInRotate(nums1,15))
40 print(Solution().searchInRotate(nums1,1))

3. basic op of BST

 1 #coding:utf-8
 2 
 3 class TreeNode:
 4     def __init__(self,x):
 5         self.val=x
 6         self.left=None
 7         self.right=None
 8     
 9 class Solution:
10     def BST_insert(self,root,node):
11         '''
12         将node节点插入以root为根的BST中
13         '''
14         if(node.val<=root.val):
15             if(root.left):
16                 self.BST_insert(root.left,node)
17             else:
18                 root.left=node
19         else:
20             if(root.right):
21                 self.BST_insert(root.right,node)
22             else:
23                 root.right=node
24 
25     def BST_search(self,root,val):
26         if(root.val==val):
27             return True
28 
29         if(root.val>val):
30             if(root.left):
31                 return self.BST_search(root.left,val)
32             else:
33                 return False
34         else:
35             if(root.right):
36                 return self.BST_search(root.right,val)
37             else:
38                 return False
39 
40     def bfs(self,root):
41         res=[]
42         if(root==None):
43             return res
44         
45         que=[]
46         que.append((root,[root.val]))
47         while(len(que)!=0):
48             size=len(que)
49             tmp=[]
50             for i in range(size):
51                 cur,path=que.pop(0)                
52                 tmp.append(cur.val)
53 
54                 if(cur.left==None and cur.right==None and sum(path)==22):
55                     print(path)
56 
57                 if(cur.left):
58                     que.append((cur.left,path+[cur.left.val]))
59                 
60                 if(cur.right):
61                     que.append((cur.right,path+[cur.right.val]))
62             res.append(tmp)
63 
64         return res
65 
66 
67 n1=TreeNode(5)
68 n2=TreeNode(4)
69 n3=TreeNode(2)
70 n4=TreeNode(6)
71 
72 s=Solution()
73 s.BST_insert(n1,n2)
74 s.BST_insert(n1,n3)
75 s.BST_insert(n1,n4)
76 
77 print(s.bfs(n1))
78 
79 
80 print("----------------------")
81 print(s.BST_search(n1,4))
82 print(s.BST_search(n1,1))