スライド1横浜国立大学.ppt

《スライド1横浜国立大学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、アルゴリズムとデータ構造補足資料4-3「2分探索」横浜国立大学理工学部数物・電子情報系学科富井尚志a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]135891619225460あらかじめ「昇順」に整列された配列a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]13589161922546019を探せ！x=a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254600i=9j=：左端：右端19を探せ！x=解の方針：「区間」と「中央」を決

2、めて、「中央」より「右」、「左」のどちらかに絞り込むa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254600i=9j=4k=(i+j)/2=※整数の演算なので小数点以下切り捨て：中央：左端：右端19を探せ！x=解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254600i=9j=4k=(i+j)/2=※整数の演算なので小数点以下切り捨て：中央：左端：右端1

3、9を探せ！x=x>a[k]:解は右にある！解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254600i=9j=4k=(i+j)/2=※整数の演算なので小数点以下切り捨て：中央：左端：右端19を探せ！x=x>a[k]:解は右にある！これより左に解はない：探索しない解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a

4、[8]a[9]1358916192254609j=4k=(i+j)/2=：右端19を探せ！x=5i=k+1=：左端右隣解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254609j=：右端19を探せ！x=5i=：左端解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むこれより左に解はない：探索しないa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1

5、358916192254609j=：右端19を探せ！x=5i=：左端7k=(i+j)/2=：中央解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むこれより左に解はない：探索しないa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254609j=：右端19を探せ！x=5i=：左端7k=(i+j)/2=：中央x

6、a[6]a[7]a[8]a[9]1358916192254606j=j-1=：右端19を探せ！x=5i=：左端7k=(i+j)/2=：中央解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む左隣これより右に解はない：探索しないa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254606j=：右端19を探せ！x=5i=：左端解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込むこれより右に解はない：探索しない5k=(i+j)/2=※整

7、数の演算なので小数点以下切り捨て：中央a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254606j=：右端19を探せ！x=5i=：左端解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む5k=(i+j)/2=※整数の演算なので小数点以下切り捨て：中央a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]1358916192254606j=：右端19を探せ！x=5i=：左端解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」

8、のどちらかに絞り込むx>a[k]:解は右にある！a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]13589161922