Cで二分探索

基本情報のお勉強の片手間に遊んでいたのをまとめる

ソースコード

serch.c

#include <stdio.h>
#include <string.h>


int compar(const void * n1, const void * n2){
    int i1, i2;
    i1 = *(int*)n1;
    i2 = *(int*)n2;
    if(i1>i2)return 1;
    if(i1<i2)return -1;
    return 0;
}

long tansaku_nibun_test(int* array, unsigned long min, unsigned long max, unsigned long value){
    unsigned long pivot = (min +max) / 2;
    if(array[pivot] == value){
        printf("探索成功(%ld)\n", pivot);
        return pivot;
    }
    if(min > max){
        printf("探索失敗\n");
        return -1;
    }
    if(array[pivot] < value){
        return tansaku_nibun_test(array, pivot + 1 , max, value);
    }
    if(array[pivot] > value){
        return tansaku_nibun_test(array, min, pivot - 1, value);
    }
    return 0;
}

unsigned long nibuntansaku(int* array, unsigned long size, unsigned long value){
    qsort(array, size, sizeof(int), compar);
    return tansaku_nibun_test(array, 0, size, value);
}

中身

標準ライブラリのqsortで中身を整頓して
そこから再帰で二分探索をしていくスタイル

まとめ

これを使ってメモリを何ギガと使ったものからの探索も、それなりのスピードでこなせたので、やっぱり先人は偉大だと感じました　まる