一、二分查詢（二分答案）

1.問題引入

有n個升序正整數ai，有q個詢問，每次輸入一個x，
求小於等於x的最大值，（資料保證有數比x小）
例如：1 3 4 6 7 9 , x=5，x=6
下標：1 2 3 4 5 6

有個遊戲叫猜數位，有一個數a，屬於【1，1000】
每次猜一個數x，會告訴你x跟a比，大了還是小了

我們令str=1，end=n，求mid=(str+end)/2
這樣區間就變成了三部分：[str,mid-1]，mid，[mid+1,end]

程式碼實現：

int main(){
	int n,q,x;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=1;i<=q;i++){
		cin>>x;
		
		int str=1,end=n,mid,ans=0;
		while(str<=end){
			mid=(str+end)/2;
			if(a[mid]<x){
				str=mid+1;
				ans=mid;
			}
			else if(a[mid]>x)end=mid-1;
			else {
				ans=mid;
				break;
			}
		}
		cout<<a[ans]<<endl;
	} 
	return 0;
}

例題1
例題2
例題3
例題4

二、排序

給定n個數，每個數分別為ai，對a[]陣列排個升序，並輸出
例：3 2 9 5 7 8 4 1 6 =>1 2 3 4 5 6 7 8 9

1.氣泡排序

讓相鄰兩個數，比較，如果前面一個數較大，就交換
3 2 9 5 7 8 4 1 6
2 3 9 5 7 8 4 1 6
2 3 9 5 7 8 4 1 6
2 3 5 9 7 8 4 1 6
2 3 5 7 9 8 4 1 6
2 3 5 7 8 9 4 1 6
2 3 4 7 8 4 9 1 6
2 3 4 7 8 4 1 9 6
2 3 4 7 8 4 1 6 9

2.sort(快速排序）

3.桶排序

陣列有對應的下標，比如a[i]中的i
我們令a[i]的值表示所有數中有多少個i
例如：1 1 4 5 7 3 2 2 2
a[1]=2，a[2]=3，a[3]=1，a[4]=1，a[5]=1，a[6]=0，a[7]=1

4.歸併排序

5.堆排序

三、遞迴