Searching algorithm.

Table of content

Binary Search

Lowest Common Ancestor of a Binary Search Tree in LeetCode

1. Searching an item in a binary search tree is O(logn).
2. The solution to the problem is given as the following

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param {TreeNode} root
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {TreeNode}
    def lowestCommonAncestor(self, root, p, q):
        ppath = get_path(root,p)
        qpath = get_path(root,q)
        f = False
        for i in xrange(min(len(ppath),len(qpath))):
            print i,ppath[i].val,qpath[i].val
            if ppath[i] != qpath[i]:
                f = True
                break
        if f: return ppath[i-1]
        else: return ppath[i]
def get_path(root,p):
    path = []
    while True:
        if root.val == p.val:
            path.append(root)
            break
        elif root.val > p.val:
            path.append(root)
            root = root.left
        elif root.val < p.val:
            path.append(root)
            root = root.right
    return path

###Search insert position in LeetCode

1. Time complexity for binary search is O(logN).
2. The solution is given as the following

class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer}
    def searchInsert(self, nums, target):
        if len(nums) == 0: return 0
        elif len(nums) == 1:
            if nums[0]>=target: return 0
            else: return 1
        else:
            return BinarySearch(nums,0,target)
def BinarySearch(nums,pos,target):
    print nums,pos,len(nums)/2
    '''
    binary serach to return a position in O(logN)
    '''
    if len(nums) == 1:
        if nums[0]>=target: return pos
        else: return pos+1
    #
    i = len(nums)/2
    if nums[i] == target: return pos+i
    elif nums[i] > target: return BinarySearch(nums[:i],pos,target)
    else: return BinarySearch(nums[i:],pos+i,target)
    pass

###Sqrt(x) in LeetCode

1. The question can be reduced into a binary search problem.
2. In particular, we should search for a base number within the range.
3. The time complexity of finding the base number is O(logN)
4. The solution is given as the following

class Solution:
    # @param {integer} x
    # @return {integer}
    def mySqrt(self, x):
        return solution(x)
def solution(x):
    if x == 0: return x
    if x <= 3: return 1
    i,j = 1,x
    while True:
        if i**2 == x: return i
        if j**2 == x: return j
        if i**2 < x and j**2 > x and j-i == 1: return i
        m = i+(j-i)/2
        print i,j,m
        if m**2 == x: return m
        if m**2 > x: i,j = i,m
        if m**2 < x: i,j = m,j        
    pass

###Pow(x,n) in LeetCode

1. The problem uses recursion approach.
2. The number of multiplication operation is O(logN).

###Minimum Size Subarray Sum in LeetCode

1. Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.