算法读书笔记第1章

第一章的主要内容

1、数据类型：布尔型、整型、字符型

(1) bool

(2) int

(3) char

(4) long

(5) Double

(6) float

(7) byte（这个是Java下的，c 中并没有）

2、语句：

(1) 声明语句例如：int a;

(2) 赋值语句    a = 1;

(3) 条件语句    if(a > 0) {} else {}

(4) 循环语句 while(){} for（）

3、数组：某一种数据类型的一个集合

4、栈和队列:存在于C 中的STL库

(1) 栈：一种先进后出的数据结构

(2) 队列：不同于栈，是先进先出的一种数据结构

5、二分查找：个人觉得这个算是第一章中最重要的一点了

(1) 基本思想：在有序的连续的数组中每次折半查找关键字，如果中间的数mid > key 则去查找它的左半部分，否则就去查找它的右半部分，最后存在返回true，否则返回false

(2) 时间复杂度：每次除以2，一半一半的下降，则O（logN）

(3) 代码：

#include<iostream>
#include<vector>
using namespace std;

class Solution
{
public:
    int BinarySearch(int key, vector<int> a)
    {
        int l = 0;
        int r = a.size()-1;
        while(l <= r)
        {
            int mid = l   (r-l)/2;
            if(key < a[mid]) r = mid-1;
            else if (key > a[mid]) l = mid 1;
            else return mid;

        }
        return -1;
    }
};


int main()
{
    vector<int> a;
    Solution s;
    for(int i = 0; i < 8; i  )
        a.push_back(i 1);
    int pos = s.BinarySearch(4,a);
    if(pos == -1)
    {
        cout<<"can't find"<<endl;
    }
    else
        cout<<a[pos]<<endl;

    return 0;
}