泛型算法-1

泛型算法实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可以用于不同类型的元素的和多种容器类型（不仅包括标准库类型，还包括内置的数组类型），以及其它类型的序列。

大多数算法都定义在头文件algorithm中

main:处理命令行

//main函数的两种定义形式
int main(int argc,char **argv[])
int main(int argc,char *argv[])

• argc:指的是命令行中输入参数的个数
• argv:一个数组，它存储了所有的命令行参数

IO库

IO库设施:

• istream类型:提供输入操作
• ostream类型:提供输出操作
• cin:一个istream对象，从标准输入读取数据
• cout:一个ostream对象，从标准输出写入数据
• cerr:一个ostream对象，通常用于输出程序错误信息，写入到标准错误
• >>运算符:用来从一个istream对象读取输入数据
• <<运算符:用来向一个ostream对象写入数据
• getline函数:从一个给定的istream读取一行数据，存入一个给定的string对象中

二分查找算法百度百科

算法效率O(log<sub>2</sub>n)（对数时间）
输入为一个有序的元素序列，如果要查找的元素包含在列表中，二分查找返回其位置，否则返回null

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

仅当列表是有序的时候，二分查找才是有效的

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# -*- coding: utf-8 -*-
# binary_search

def binary_search(list_1, item):

    low = 0
    high = len(list_1)-1

    while low <= high:
        '''使用 // 整除运算符可以不用int进行类型转换'''
        #每次都检查中间的元素
        mid = (low + high)/2
        guess = list_1[int(mid)]

        if guess == item:
            return int(mid)#返回所在位置的索引
        if guess < item:   #猜的数字小了，修改low
            low = mid+1
        if guess > item:   #猜的数字大了，修改high
            high = mid-1
    return None

def main():

    list_2 = [1,2,3,4,5,6,7,8,9]

    print(binary_search(list_2, 8))
    print(binary_search(list_2, 10))

main()

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

int binary_search(int a[9],int n,int x)//n为元素个数 
{
    int mid;
    int high,low=0;
	int guess;
	
    high = n-1;//数组下标从0开始 
    
	while(low <= high)
    {
        mid = (high+low)/2;
        guess = a[mid];
        if(guess == x)
            return mid;
        if(guess > x)
            high = mid-1;
		if(guess < x)
		    low = mid+1; 
    }
    return -1;
}

int main()
{
	int temp;
    int a[9] = {1,2,3,4,5,6,7,8,9}; 
	
	cout<<sizeof(a)/sizeof(int)<<endl;
	cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
    temp = binary_search(a,sizeof(a)/sizeof(int),5);
	cout<<temp<<endl;
	
	return 0;	
}

类型名获取