树(tree)、查找练习（increase slowly )

   发现自己真的很笨，理解一个概念都要半天！以前数学还行，但是读大学后就变笨了，不愿意去思考，玩魔兽也不动脑筋、讲究技巧。所以脑袋生锈了，是时候需要训练大脑了，整天看一些无聊的视频会懒惰的，而且整天不锻炼身体也会懒惰的，不仅身体懒惰，而且大脑越来越不行，我就是一个典型！不管怎么样，能理解多少算多少，多练习就好了，多开拓思维，过两天找同学给我补习数学去....

  1、并查集:

//============================================================================
// Name        : Union-find.cpp
// Author      : hl
// Version     :
// Copyright   : Your copyright notice
// Description : Union_find in C++, Ansi-style
//============================================================================

#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;

int father[50002],a,b,m,n,p;
/*
 * 并查集
 * 理解(simple)：
 *    亲戚(Relations)
 *    题目描述： 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
 *    输入格式 Input Format
 *        第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。
 *        接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
 *    输出格式 Output Format
 *        P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
 * 结果（简单理解）---经过以下分析/最终我们需要找到Pi和Pj的根为同一个就OK了!!!
 * Please input some information:
1000,3,1
1,2              ----1, 2直接找到返回；a[1] = 2,a[2] = 2;
-----x1
-----father[x]1
-----x2
-----father[x]2
2,3              ----2, 3直接找到返回；a[1] = 2, a[2] = 3, a[3] = 3;
-----x2
-----father[x]2
-----x3
-----father[x]3
1,4              ----1不能直接找到，a[1] = 2, 递归a[2] = 3, a[3] = 3,到3找到返回a[3];
-----x3          ----4直接找到返回;最后，a[1] = 2, a[2] = 3, a[3] = 4， a[4] = 4;
-----father[x]3
-----x2
-----father[x]3
-----x1
-----father[x]3
-----x4
-----father[x]4
3,4            ******当我们寻找3,4和亲戚关系的时候；可以通过a[3]找到4，因此3的父亲是4，and 4就是它本身；到此找到亲戚关系！！！
-----x4        ******比如是1，5；通过1，我们找到root为4,而通过5找到的root是5；
-----father[x]4
-----x3
-----father[x]4
-----x4
-----father[x]4
Yes
 */
//查找(find)：寻找某一个元素所在集合的根。使用路径压缩来优化该函数。
int find(int x)
{
    if(father[x]!=x) father[x]=find(father[x]);
    cout << "-----x" << x << endl;
    cout << "-----father[x]" << father[x] << endl;
    return father[x];
}

int main() {
    cout << "Please input some information: " << endl;
#if 1
    scanf("%d,%d,%d",&n,&m,&p);
    //getchar();
    for(int i=1;i<=n;i++) father[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d,%d",&a,&b);
        //getchar();
        a=find(a),b=find(b);father[a]=b;
    }
    for(int i=1;i<=p;i++)
    {
        scanf("%d,%d",&a,&b);
        //getchar();
        a=find(a);b=find(b);
        if(a==b)printf("Yes\n");
        else printf("No\n");  //Result is YESYESNO or like this struct? about buffer,
    }
#endif
    return 0;
}

 2、二分查找:

/*
 ============================================================================
 Name        : search.c
 Author      : hl
 Version     :
 Copyright   : Your copyright notice
 Description : Search in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 打印整型数组 can be used for test
 */
void print_array(int a[], int len)
{
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", a[i]);
    putchar('\n');
}

/* 时间复杂度（）
 * 说明：
 * 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；
 * 其缺点是要求待查表为有序表，且插入删除困难;
 * So，折半查找方法适用于不经常变动而查找频繁的有序列表--百度百科
 */
int binarysearch(int a[], int len, int number)
{
    int mid, start = 0, end = len - 1;

    while (start <= end)
    {
        mid  = (start + end) / 2;  //record middle position
        if (a[mid] < number)
            start = mid + 1;       //注意mid+1哦！否则可能会死循环（没+1,sometime 怎么结束?能找到数组最后一位吗?）
        else if (a[mid] > number)
            end = mid - 1;         //注意mid-1哦！否则可能会死循环（没-1,sometime 怎么结束?能找到数组的第一位吗?）
        else
            return mid;
    }
    return -1;
}

int main(void) {
    int a1[7] = {3, 4, 5, 7, 9, 10, 12};
    int key = 12;
    printf("Search number %d, got position a[%d]\n", key, binarysearch(a1, 7, key));

    return EXIT_SUCCESS;
}