算法业计与分祈 例1.1 ◆A[1.101={1,3,56,7,10,2,273456} ◆在A中搜索x=22 算法设计与分析
算法设计与分析 6 w A[1…10]={1,3,5,6,7,10,22,27,34,56} w 在A中搜索x＝22 例1.1
算法计与分祈 算法1.1 ◆/ Linearsearch j←1 ◆ While(j<n)and(X≠A[j ◆1←j+1 ◆ End while -Ifx=AlI then return j else return 0 算法设计与分析
算法设计与分析 7 算法1.1 w Linearsearch w j←1 w While（j<n) and (x≠A[ j]) w j ← j+1 w End while w If x=A[j] then return j else return 0
算法业计与分析 例1.2 template<class T> int Max(t al, int n) W寻找a[0:n-1中的最大无素 Int pos=0, fr(inti=1;i<n;计+) 八( alpos]< a[ POs =I, return pos 算法设计与分析
算法设计与分析 8 例1.2 template<class T> int Max(T a[], int n) {// 寻找a [ 0 : n - 1 ]中的最大元素 int pos = 0; for (int i = 1; i < n; i++) if (a[pos] < a[i]) pos = i; return pos; }
算法业计与分祈 二分搜索 算法12) inarysearch 0 W<l, high←n←0 while(lowshigh)and(=g mdL( thigh)/2」 ifx=A[mid] then J←mid else if X<A[mid] then high +-mid-4 else low←mid+1 end while return 算法设计与
算法设计与分析 9 w 算法1.2 binarysearch w low ←1;high ←n;j ←0 w while (low≤high) and (j=0) w mid ← (low+high)/2 w if x=A[mid] then j ←mid w else if x<A[mid] then high ←mid-1 w else low ←mid+1 w end while w return j 二分搜索
算法业计与分析 23 15 32 12 22 35 ◆Logn+1 10 算法设计与分析
算法设计与分析 10 1 10 27 4 5 7 22 8 9 15 23 12 32 35 w Logn +1