« はじめてのC ー型宣言の思い出ー | トップページ | キャラメルボックス 2019 スプリングツアー 「スロウハイツの神様」 »

2019年3月15日 (金)

はじめてのC 〜二分探索を三項演算子で書く悪魔〜

プログラムのコーディングは設計者の特徴(クセ)が出やすいものです。


そこで、なるべく「分かりやすい」&「保守しやすい」

コーディングを心がけてもらうように、

マネージャーはコーディングする設計者に指示を出すのだが。。。


二分探索(binary search)をご存知だろうか?


二分探索とは、

ソート済みの配列に入ったデータ(同一の値はない)に対する検索をするとき、

中央の値を見て、検索したい値との大小関係を比較し、

検索したい値が中央の値の右側にあるか、

左側にあるかを判断して、

片側には存在しないことを確かめながら検索していく手法(アルゴリズム)です。


この手法だと、

配列n個のデータの中央の値を見ますので、

1回の操作でn/2個程度の要素を無視することができます。

(時間計算量は、log2 n)


詳しい内容は、ググってください。

簡単に言うと、「探索時間が早い」処理方法と思ってください。


この二分探索のC言語のコーディングは、一般的に以下のように

関数の再帰呼び出しを使って行います。


int binary_search(int list[], int key, int min, int max) {

    if (max < min) {

        return -1;

    } else {

        int mid = min + (max - min) / 2;

        if (list[mid] > key) {

            return binary_search(list, key, min, mid - 1);

        } else if (list[mid] < key) {

            return binary_search(list, key, mid + 1, max);

        } else {

            return mid;

        }

    }

}


が?!

私が驚愕したのは、二分探索を三項演算子で書く悪魔。


例えば、yが1〜6までのどの値かxに求める式を


int x = (y < 4) ? ((y < 2) ? 1 : (y < 3) ? 2 : 3) : (y < 6) ? ((y < 5) ? 4 : 5) : 6 );


もはや呪文。(・_・)エッ....?

« はじめてのC ー型宣言の思い出ー | トップページ | キャラメルボックス 2019 スプリングツアー 「スロウハイツの神様」 »

パソコン・インターネット」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック


この記事へのトラックバック一覧です: はじめてのC 〜二分探索を三項演算子で書く悪魔〜:

« はじめてのC ー型宣言の思い出ー | トップページ | キャラメルボックス 2019 スプリングツアー 「スロウハイツの神様」 »

フォト
無料ブログはココログ

bigmoroの関連リンク