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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

アルゴリズム

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

Q&A

解決済

3回答

2943閲覧

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

nsd24

総合スコア9

C

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

アルゴリズム

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

0グッド

0クリップ

投稿2018/06/27 09:33

前提・実現したいこと

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

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

c

1#include<stdio.h> 2#include<stdlib.h> 3 4#define N 10 5 6void print_data(int *a); 7void Insert_Sort(int a[]); 8 9int binsearch(int a[],int n,int key); 10 11int main(void) 12{ 13 int a[N]; 14 int i,key,ans; 15 16 //データの生成 17 srand((unsigned int)time(NULL)); 18 for(i=0;i<N;i++){ 19 a[i]=rand()%10; 20 } 21 22 Insert_Sort(a); 23 24 printf("生成データ:\n"); 25 print_data(a); 26 27 printf("探索key(0から9の間の数)を教えて> "); 28 scanf("%d",&key); 29 30 ans=binsearch(a,N,key); 31 32 printf("keyの場所は%d番目だよ\n",ans); 33 34 return 0; 35} 36 37void print_data(int *a) 38{ 39 int i; 40 41 for(i=0;i<N;i++){ 42 printf("%d\t",*(a+i)); 43 } 44 printf("\n"); 45} 46 47void Insert_Sort(int a[]) 48{ 49 int i,x,t; 50 51 for(i=1;i<N;i++){ 52 x=a[i]; 53 t=i; 54 while(x<a[t-1] && t>0){ 55 a[t]=a[t-1]; 56 t--; 57 } 58 a[t]=x; 59 } 60} 61 62int binsearch(int a[],int n,int key) 63{ 64 int left=0; 65 int right=n-1; 66 int mid; 67 68 //printf("while前\n"); 69 //printf("n=%d key=%d left=%d right=%d mid=%d\n",n,key,left,right,mid); 70 71 while(left<=right){ 72 mid=left+(right-left)/2; 73 //printf("while中\n"); 74 //printf("n=%d key=%d left=%d right=%d mid=%d\n",n,key,left,right,mid); 75 if(a[mid]>key){ 76 right=mid-1; 77 } 78 else if(a[mid]<key){ 79 left=mid+1; 80 } 81 else if(a[mid]==key && a[mid-1]!=key){ //(a) 82 return mid; 83 } 84 else{ 85 right--; //(b) 86 } 87 } 88 //printf("while後\n"); 89 //printf("n=%d key=%d left=%d right=%d mid=%d\n",n,key,left,right,mid); 90 return -1; 91}

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

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

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

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

bcc devloperを使用

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

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

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

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

c

1int myBinSearch(int array[], int key) { 2 int index = binsearch(array, N, key); 3 return findTopIndex(array, index); 4} 5int binsearch(int array[], int n, int key) { 6 // 普通の二分探索の実装でOK 7} 8int findTopIndex(int array[], int index) { 9 for(int i = index - 1;i >= 0;i --) { 10 if(array[i] != array[i + 1]) return i + 1; 11 } 12 return 0; 13} 14

投稿2018/06/27 09:52

編集2018/06/28 04:09
takezoux2

総合スコア3

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

  • index値が配列をオーバーランしていないか
  • array[index]は探索キーと一致するか

を追加してあげれば、期待する動作になると思います。

c

1int bs_lower_bound(int a[], int n, int key) { 2 int l = 0; 3 int h = n; // Not n - 1 4 while (l < h) { 5 int mid = (l + h) / 2; 6 if (key <= a[mid]) { 7 h = mid; 8 } else { 9 l = mid + 1; 10 } 11 } 12 13 if (l != n && a[l] == key) 14 return l; 15 return -1; 16} 17

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

投稿2018/06/28 03:39

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

投稿2018/06/27 12:05

HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問