AppleScriptでアルゴリズム(1): バイナリーサーチ

説明

MacOSXに標準で付属するAppleScriptを使用して、アルゴリズムの勉強を行います。

バイナリーサーチ

まずバイナリーサーチです。

AppleScript: binary search

実行結果

(*Search for 1*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 1, 2, 3, 6*)
(*values length is 4*)
(*mid index is 2*)
(*mid vlaue is 2*)
(*value is 1, 2*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 1*)
(*The search value[1] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 2*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 1, 2, 3, 6*)
(*values length is 4*)
(*mid index is 2*)
(*mid vlaue is 2*)
(*The search value[2] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 3*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 1, 2, 3, 6*)
(*values length is 4*)
(*mid index is 2*)
(*mid vlaue is 2*)
(*value is 3, 6*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 3*)
(*The search value[3] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 4*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 1, 2, 3, 6*)
(*values length is 4*)
(*mid index is 2*)
(*mid vlaue is 2*)
(*value is 3, 6*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 3*)
(*4,  not found.*)
(*Search for 5*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 1, 2, 3, 6*)
(*values length is 4*)
(*mid index is 2*)
(*mid vlaue is 2*)
(*value is 3, 6*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 3*)
(*5,  not found.*)
(*Search for 6*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*The search value[6] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 7*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 7, 9*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 7*)
(*The search value[7] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 8*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 7, 9*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 7*)
(*8,  not found.*)
(*Search for 9*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*The search value[9] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 10*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 11, 13, 15*)
(*values length is 3*)
(*mid index is 1*)
(*mid vlaue is 11*)
(*10,  not found.*)
(*Search for 11*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 11, 13, 15*)
(*values length is 3*)
(*mid index is 1*)
(*mid vlaue is 11*)
(*The search value[11] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 12*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 11, 13, 15*)
(*values length is 3*)
(*mid index is 1*)
(*mid vlaue is 11*)
(*value is 13, 15*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 13*)
(*12,  not found.*)
(*Search for 13*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 11, 13, 15*)
(*values length is 3*)
(*mid index is 1*)
(*mid vlaue is 11*)
(*value is 13, 15*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 13*)
(*The search value[13] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)
(*Search for 14*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 11, 13, 15*)
(*values length is 3*)
(*mid index is 1*)
(*mid vlaue is 11*)
(*value is 13, 15*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 13*)
(*14,  not found.*)
(*Search for 15*)
(*value is 1, 2, 3, 6, 7, 9, 11, 13, 15*)
(*values length is 9*)
(*mid index is 4*)
(*mid vlaue is 6*)
(*value is 7, 9, 11, 13, 15*)
(*values length is 5*)
(*mid index is 2*)
(*mid vlaue is 9*)
(*value is 11, 13, 15*)
(*values length is 3*)
(*mid index is 1*)
(*mid vlaue is 11*)
(*value is 13, 15*)
(*values length is 2*)
(*mid index is 1*)
(*mid vlaue is 13*)
(*The search value[15] is found in 1, 2, 3, 6, 7, 9, 11, 13, 15.*)