程式設計-- Binary Search 通訊一甲 B09622048 楊穎穆.

Presentation on theme: "程式設計-- Binary Search 通訊一甲 B09622048 楊穎穆."— Presentation transcript:

1 程式設計-- Binary Search 通訊一甲 B 楊穎穆

2 目錄 1.目的 2.原理 3.流程圖 4.程式 5.實驗結果顯示 6.參考資料

3 目的 1. 試輸入n個未排序的整數到陣列中 2. 嘗試把未排序的整數到陣列中之數值依照陣列位置與值印出
3. 嘗試用快速排序(Quick Sort)法把陣列中之數值由小而大地排序 4. 嘗試把排序後的整數到陣列中之數值依照陣列位置與值印出 5. 試輸入一個陣列中的值,使用二元搜尋(Binary Search)找到此值在陣列的所在位置並把此位置印出

4 原理 假如資料本身是經過排序的，在搜尋時可以利用二元的方法，每次都把陣列分成兩半，然後從其中的一半繼續搜尋，這種方法叫做「二元搜尋」(Binary search)，首先，陣列裡的元素要排序，然後等分成兩個陣列，由於陣列已排序過，搜尋的值只會存在於其中的一個陣列中，只要比較搜尋鍵和二元陣列中的極值（也就是最大值或最小值），就知道要搜尋的值位於那個陣列中，然後繼續在那個陣列中進行二元搜尋。

5 原理 11 6 8 16 3 A[0] A[1] A[2] A[3] A[4] 3 6 8 11 16

6 流程圖 main Input x L<=R i= (L+R)/2 X=A[i] 印出 i L=i R=i end

7 程式 #include <stdio.h> #include <stdlib.h> #define n 8
int Partition(int a[],int p, int r){ int s,j,temp; int x=a[r]; int i=p-1; for(j=p;j<r;j++){ if(a[j]<=x){ i++; if(i !=j){ temp=a[i]; a[i]=a[j]; a[j]=temp; }

8 temp=a[i+1]; a[i+1]=a[j]; a[j]=temp; printf("\n"); for(s=0;s<n;s++) printf(" %d",a[s]); return i+1; } int quicksort(int a[],int p,int r){ int q; if(p<r){ q=Partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,p);

9 int main(void){ int t,A[n],i,x; int l,r,mid; for(t=0;t<n;t++){ printf(" 請輸入任意數字[%d]:",t); scanf("%d",& A[t]); } quicksort(A,0,n-1); printf("\n由小到大排序後的數字[%d]: ",t); printf("%d \n",A[t]);

10 printf("\n隨意輸入一個數:"); scanf("%d",&x); l=0; r=9; mid=l+(r-l)/2; while((l<r)&&(A[mid]!=x)){ if(A[mid]>x) r=mid-1; else if(A[mid]<x) l=mid+1; } if(A[mid]==x) printf("位址在 A[%d]",mid); else printf("\n找不到"); system("PAUSE"); return 0;

11 實驗結果顯示

12 實驗結果顯示

13 實驗結果顯示

14 參考資料 主要的參考資料來至”演算法概論”這本書及王志湖老師上課所教授的內容。

15 END