線形探索のプログラムを基に二分探索のプログラムを作成

前提・実現したいこと

現在辞書ファイルの検索を行うプログラムを作成中で線形探索と二分探索で辞書ファイルの検索を行おうと考えています。線形探索の方はうまくいったのですが、それをもとにした二分探索のプログラムを作成する際にどうしても手詰まりになってしまいます。このソースコードのどこを編集すれば二分探索としてのプログラムが完成するでしょうか。

該当のソースコード

C
1/*線形探索のプログラム*/
2#include <stdio.h>
3#include <stdlib.h>
4typedef struct {
5  unsigned char s[24];
6} word;
7int main(int argc, char **argv) {
8  word dict[100000];
9  FILE *fp;
10  int i = 0,c,k;
11  fp = fopen(argv[1],"r");
12  if (argc < 2) {
13    fprintf(stderr,"usage: ./a.out dictFile\n"); exit(1);
14  }
15  if ((fp=fopen(argv[1],"r")) == NULL) {
16    fprintf(stderr,"can't open file %s\n",argv[1]); exit(1);
17  }
18  k=0;
19  while((c=fgetc(fp)) != EOF) {
20    if (c == '\n') {
21      dict[i].s[k] = 0;
22      i++;
23      k=0;
24    } else {
25      dict[i].s[k] = c;
26      k++;
27    }
28  }
29  int linecount = i;
30  fclose(fp);
31  unsigned char s[30], *p, *r;
32  while(fgets(s,30,stdin) != EOF) {
33  for(p = s ; *p != 0 ; p++) {
34    if(*p == '\n') {
35      *p = 0;
36    }
37  }
38
39  for(i = 0 ; i < linecount ; i++) {
40    p = s;
41    r = dict[i].s;
42    while((*p == *r) && (*p != 0) && (*r != 0)) {
43      p++;r++;
44    }
45    if((*p == 0) && (*r == 0)) {
46      printf("%d\n", i+1);
47      break;
48    }
49  }
50
51  if(i == linecount) {
52    printf("-1\n"); continue;
53  }
54  }
55  return 0;
56}
57

試したこと

途中にint lower=0とint upper=linecount、それをもとにしたint mid = lower + upper / 2 をつけ足してみようと考えたのですが二分探索のへの生かし方が分からなかったです。

hoshi-takanori

2020/06/07 21:32

「どこを編集すればいいか」という質問の答えとしては後半の for(i = 0 ; i < linecount ; i++) のループでしょうね。なお、課題 (ですよね？) を提出して単位が欲しいだけでなく、本気でプログラミングを上達したいなら、まずインデントが微妙にズレてるのを修正したり、関数を分割することをお勧めします。