# HW1 - Q2
###### tags: `演算法`, `109-2`

:::success
當周小組作業 https://hackmd.io/kweMwbO1RdyFdvQoZxe8XQ
:::

## Question
Design a data structure to represent a set with elements being positive integers, and then design algorithms for the following operations:
- Compute the union of two sets.
- Compute the intersection of two sets.
- Determine if a given element is in a given set.

## Mein Answer
<!--  -->

### Designed Data Structure:
- Sorted Linked List

### Union
- O(n) operation

Union(SortedLinkedlist a, SortedLinkedList b)
    let i = 0
    let j = 0
    let current =  0
    let result = []
    while(i < a.length || j < b.length)
        if(j >= b.length || (i < a.length && a[i] <= b[j]) )
            current = a[i]
            push a[i] into result
            i++
        else
            current = b[j]
            push b[j] into result 
            j++
    return result

:::spoiler JavaScript

function Union(a, b)
{
    let i = 0
    let j = 0
    let current =  0
    let result = []
    while(i < a.length || j < b.length)
    {
        if(j >= b.length || (i < a.length && a[i] <= b[j]) )
        {
            current = a[i]
            result.push(a[i])
            i++
        }
        else
        {
            current = b[j]
            result.push(b[j]) 
            j++
        }
    }
    return result
}
Union([1,3,5,7], [2,3,4,5])

:::

### Intersection
- O(n) operation

Intersection(SortedLinkedlist a, SortedLinkedList b)
    let i = 0
    let j = 0
    let current =  0
    let result = []
    while(i < a.length || j < b.length)
        if(j >= b.length || (i < a.length && a[i] <= b[j]) )
            if(current == a[i])
                push a[i] into result
            current = a[i]
            i++
        else
            if(current == b[j])
                push b[j] into result
            current = b[j]
            j++
    return result

:::spoiler JavaScript

function Intersection(a, b)
{
    let i = 0
    let j = 0
    let current =  0
    let result = []
    while(i < a.length || j < b.length)
    {
        if(j >= b.length || (i < a.length && a[i] <= b[j]) )
        {
            if(a[i] == current)
                result.push(a[i])
            current = a[i]
            i++
        }
        else
        {
            if(b[j] == current)
                result.push(b[j]) 
            current = b[j]
            j++
        }
    }
    return result
}
Intersection([1,3,5,7], [2,3,4,5])

:::

### Find
- Binary search
- O(logn) operation

Find(SortedLinkedlist a, int element)
    let i = 0
    let lbound = 0
    let rbound = a.length - 1
    
    while(lbound != rbound)
        i = (lbound + rbound) / 2 
        round i to an Integer
        
        if(a[i] == element)
            return i;
        else if(a[i] < element)
            lbound = i
        else
            rbound = i
    
    return null // Not found

:::spoiler Javascript

function Find(a, element)
{
    let i = 0
    let lbound = 0
    let rbound = a.length - 1
    
    while(rbound - lbound > 1 || rbound == 0)
    {
        i = Math.round( (lbound + rbound) / 2 )
        
        if(a[i] == element)
            return i;
        else if(a[i] > element)
            rbound = i
        else
            lbound = i
    }
    return null // Not found
}
Find([0,1,2,3,4,5,6,7], 5)

:::