C++ Бинарные ключевые слова поиска

Question

есть. Я пытаюсь подсчитать ключевые слова в файле, используя двоичный поиск. Однако в некоторых случаях функция возвращает правильный индекс, а в других случаях он просто не может получить индекс. И я не знаю, почему. Вот мой код:

---

GlobalsDefine.h

#pragma once 
#define MAXLEN 10 
#define TOTAL 32  
#define HASHLEN 41 

extern const char* KeyWords[TOTAL]; 

---

BiSearch.h

#ifndef BISEARCH_H 
#define BISEARCH_H 
#include <iostream> 
#include <cstring> 
#include <iomanip> 
#include "GlobalsDefine.h" 
using namespace std; 


class SeqWords 
{ 
public: 
    char keyword[MAXLEN]; 
    int length; 
    int count; 
}; 

int BiSearch(char* des, const char** src, int begin, int last);   
void initKeyWords(SeqWords* SW); 

#endif // BISEARCH_H 

---

BiSearch.cpp

#include "BiSearch.h" 
SeqWords SW[TOTAL]; 
int BiSearch(char* des, const char** src, int begin, int last) 
{ 
    int result = -1; 
    while(begin <= last) 
    { 
     int mid = (begin + last)/2; 
     if(strcmp(src[mid],des) > 0) 
      last = mid - 1; 
     else if(strcmp(src[mid],des) < 0) 
      begin = mid + 1; 
     else 
     { 
      if(result < mid) 
       result = mid; 
      begin = mid + 1; 
     } 
    } 
    return result; 
} 


void initKeyWords(SeqWords* SW) 
{ 
    for(int i = 0; i < TOTAL; i++) 
    { 
     strcpy(SW[i].keyword,KeyWords[i]); 
     SW[i].length = strlen(SW[i].keyword); 
     SW[i].count = 0; 
    } 
} 

---

main.cpp

#include <iostream> 
#include <cstring> 
#include "BiSearch.h" 
#include "GlobalsDefine.h" 
using namespace std; 
const char* KeyWords[TOTAL] = 
{ 
    "auto","double","int","struct","break","else","long","switch", 
    "case","enum","register","typedef","char","extern","return","union", 
    "const","float","short","unsigned","continue","for","signed","void", 
    "default","goto","sizeof","volatile","do","if","while","static", 
}; 

int main() 
{ 
    extern SeqWords SW[TOTAL]; 
    initKeyWords(SW); 
    cout << BiSearch("if", KeyWords, 0, TOTAL) << endl; 
    cout << BiSearch("for", KeyWords, 0, TOTAL) << endl; 
    return 0; 
} 

---

Результаты:

29 
-1 

Answer 1

бинарный поиск требует массив будет отсортирован, который не ваш случай.

Live Demo с отсортированного входом, и с фиксированным сайта вызывающему (last не TOTAL но TOTAL - 1)

Answer 2

Для выполнения двоичного поиска правильно поиска вектора (ключевые слова в вашем случае) должны быть правильно отсортирован. И это не так в вашем примере, так как у вас есть «break» после «struct», например.

Answer 3

Двоичный поиск работает только на отсортированных массивах, чтобы ваш код работал, вам нужно сначала отсортировать KeyWords.