Rubyのパフォーマンスが足りない時に、C言語で書かれたライブラリを呼び出すことが便利です。
ただ、Rubyが使えるC言語のライブラリの書き方は、普通のライブラリと少し異なり、
シンプルな二分探索を実装しながら、CとRubyのインターフェースを可能とするRuby C Apiを紹介したいと思います。

Makefileの作成

まず、Rubyが必要とする複数のC言語のファイルを自動で作成してもらいました。
作業するフォルダにて、extconf.rbというファイルに、以下の内容を記入しました。

#!/usr/bin/env ruby
require 'mkmf'
# preparation for compilation goes here
create_header
create_makefile 'c_alg'

extconf.rbをrubyで実行すると、extconf.hとMakefileが作成されます。
今回のライブラリですと、そのファイルの上書きまたは変更が不要です。
加えて、二分探索の関数自体が入っている、c_alg.cというファイルを手動で作成しなければなりません。

データ型周り

C言語はそのままRubyの変数を読み込むことができません。
同様に、C言語から返される変数は、そのままRubyのスクリプトに使われるとおかしい値が出てしまいます。
原則として、Rubyのスクリプトが渡す変数は、C言語から見ると、Ruby C Apiが定義するVALUEというデータ型になります。
ただ、VALUEはRuby C Apiにしか存在しないので、VALUEを、標準Cライブラリを含むその他ライブラリが使えるデータ型（int、char、など）に変換する必要があります。
その際に、NUM2INT, NUM2FLOAT, INT2NUMなどの関数が使えます。

二分探索

以下、c_alg.cにて、Rubyのスクリプトが呼び出せる、とてもシンプルな二分探索のアルゴリズムを実装しました。

#include <ruby.h> // Ruby C Api
#include "extconf.h"
// Rubyの配列をC言語が読み込める配列に変換
// Rubyは配列を変換する関数を提供してくれないので、手動で処理します。
int *convert_to_c_array(VALUE ruby_array, int len) {
  int *c_array = (int *)malloc(sizeof(int) * len);
  for (int i = 0; i < len; i++) {
    VALUE rb_num = rb_ary_entry(ruby_array, i);
    c_array[i] = NUM2INT(rb_num);
  }
  return c_array;
}

VALUE c_binary_search(VALUE self, VALUE ruby_array, VALUE ruby_target) {
  int len = (int)RARRAY_LEN(ruby_array); // RARRAY_LENは配列の長さを返す、Ruby C Apiの関数です。
  int target = NUM2INT(ruby_target);
  int *c_number_array = convert_to_c_array(ruby_array, len); // Cが読み込める配列に変換
  int low = 0;
  int high = len -1;
  int i = len / 2;
  while (c_number_array[i] != target) {
    if (c_number_array[i] < target) {
        low = i + 1;
    } else {
        high = i - 1;
    }
    i = low + (high - low) / 2;
  }
  // Rubyが読み込める変数に変換
  return INT2NUM(i);
}

ご覧の通り、データ型の変更以外、あくまでも変哲のないC言語になります。

init関数

今ライブラリをコンパイルし、Rubyのスクリプトでc_binary_search呼び出してもエラーが発生してしまいます。
理由は、c_binary_searchが存在しても、Rubyが使えるものとしてはエクスポートされていないからです。
よって、c_binary_searchをエクスポートする関数を追加しました。

void Init_c_alg() {
  VALUE module = rb_define_module("CAlg"); // モジュール名を定義
  // Rubyのメソッドを定義
  // 引数は順番で、モジュール名、Rubyに呼び出される関数名、エクスポートされる関数、selfを除く引数の数
  rb_define_method(module, "c_binary_search", c_binary_search, 2);
}

今ライブラリをコンパイルし、スクリプトにインポートすれば、なんのエラーもありません。
例えば、ライブラリファイルがあるフォルダにて、以下の内容が記載されているtest.rbファイルを実行すれば1が返されます。

require './c_alg'
include CAlg
array = [1, 2, 4, 5, 6, 7, 8, 9];
a = c_binary_search(array, 2)
print a

終わりに

関数が一つしかない、とてもシンプルなライブラリを作成しました。
もちろん、ファイルや関数が多く、複雑なライブラリの開発も可能です。
ユースケースが多く、とても便利なRubyやRuby on Railsを拡張する方法だと思います。