質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.33%

  • C

    3997questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • アルゴリズム

    428questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

該当するものが複数ある場合の二分探索(C言語)

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 668

nsd24

score 3

 前提・実現したいこと

二分探索法で、探索キーと一致する複数の配列要素の添え字のうち最も小さい添え字を返す関数を作成したいです。(※c言語)

 発生している問題・エラーメッセージ

#include<stdio.h>
#include<stdlib.h>

#define N 10

void print_data(int *a);
void Insert_Sort(int a[]);

int binsearch(int a[],int n,int key);

int main(void)
{
    int a[N];
    int i,key,ans;

    //データの生成
    srand((unsigned int)time(NULL));
    for(i=0;i<N;i++){
        a[i]=rand()%10;
    }

    Insert_Sort(a);

    printf("生成データ:\n");
    print_data(a);

    printf("探索key(0から9の間の数)を教えて> ");
    scanf("%d",&key);

    ans=binsearch(a,N,key);

    printf("keyの場所は%d番目だよ\n",ans);

    return 0;
}

void print_data(int *a)
{
    int i;

    for(i=0;i<N;i++){
        printf("%d\t",*(a+i));
    }
    printf("\n");
}

void Insert_Sort(int a[])
{
    int i,x,t;

    for(i=1;i<N;i++){
        x=a[i];
        t=i;
        while(x<a[t-1] && t>0){
            a[t]=a[t-1];
            t--;
        }
        a[t]=x;
    }
}

int binsearch(int a[],int n,int key)
{
    int left=0;
    int right=n-1;
    int mid;

    //printf("while前\n");
    //printf("n=%d key=%d left=%d right=%d mid=%d\n",n,key,left,right,mid);

    while(left<=right){
        mid=left+(right-left)/2;
        //printf("while中\n");
        //printf("n=%d key=%d left=%d right=%d mid=%d\n",n,key,left,right,mid);
        if(a[mid]>key){
            right=mid-1;
        }
        else if(a[mid]<key){
            left=mid+1;
        }
        else if(a[mid]==key && a[mid-1]!=key){       //(a)
            return mid;
        }
        else{
            right--;                            //(b)
        }
    }
    //printf("while後\n");
    //printf("n=%d key=%d left=%d right=%d mid=%d\n",n,key,left,right,mid);
    return -1;
}


上記のコード中にある(a)、(b)部分をのみを変えて動くようにしたいです。
今のままだと、mid=0のときに(a)部分のa[mid-1]がアンダーフローしてしまいます。

(a)、(b)部分以外にも条件式を加えるとできるのですが、(a)、(b)部分のみをいじり、アンダーフローを避けることができないです。

どうかご教授よろしくお願いいたします。

 補足情報(FW/ツールのバージョンなど)

bcc devloperを使用

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+1

2つの機能を混ぜて実装するのは複雑になるだけなので

  • 二分探索
  • 二分探索で見つけたindexから前をたどって、同じ値の最も小さいindexをみつける

の2つの機能に分けた方が良いです。実用上の計算量は0(log n)で二分探索と変わりません。(最悪計算量は、すべての要素が同じ値の場合、この実装ではO(n)になる可能性があります。)

int myBinSearch(int array[], int key) {
    int index = binsearch(array, N, key);
    return findTopIndex(array, index);
}
int binsearch(int array[], int n, int key) {
    // 普通の二分探索の実装でOK
}
int findTopIndex(int array[], int index) {
    for(int i = index - 1;i >= 0;i --) {
      if(array[i] != array[i + 1]) return i + 1;
    }
    return 0;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

a)の条件式のうち右の条件は、midがゼロである場合であれば不要でないですか?

つまり、左の条件&&(midがゼロ丨丨右の条件)でだめですか?動作未確認。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

c++のlower_boundを参考にしてみるのはどうでしょうか。
この関数は「配列内で、探索キー以上の値が現れる最初のindex値を返す」という挙動になります。

  • index値が配列をオーバーランしていないか
  • array[index]は探索キーと一致するか
    を追加してあげれば、期待する動作になると思います。
int bs_lower_bound(int a[], int n, int key) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid = (l + h) / 2;
        if (key <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }

    if (l != n && a[l] == key)
        return l;
    return -1;
}

lower_boundは、ココにあった物を使用させてもらいました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • C

    3997questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • アルゴリズム

    428questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。