前提・実現したいこと
二分探索法で、探索キーと一致する複数の配列要素の添え字のうち最も小さい添え字を返す関数を作成したいです。(※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を使用
回答3件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。