Проблемы с функцией двоичного поиска

Question

Проблемы с функцией binary_search, перечисленные в верхней части. не уверен, куда идти. Я не очень хорошо разбираюсь в бинарном поиске.

#include <iostream> 
#include <cstdlib> 
#include <fstream> 

using namespace std; 

void get_input(ifstream& fin, int a[], int size, int & array_size); 

void binary_search (int a[], int & array_size) 
{ 
    cout << "Please enter the element you would like to search for \n"; 
    int element; 
    cin >> element; 

    int lastindex=array_size-1, startindex=0; 

    while (startindex <= lastindex) 
    { 
     int midindex=(array_size/2); 
     if(element > a[midindex]) 
     { 
      startindex=midindex; 
     } 
     else if (element < a[midindex]) 
     { 
      lastindex=midindex-1; 
     } 

    } 

} 

int main() 
{ 
    int array_size=-1; 
    int a[100]; 

    ifstream fin; 

    get_input (fin, a, 100, array_size); 

    binary_search (a, array_size); 

    return 0; 
} 

void get_input (ifstream& fin, int a[], int size, int & array_size) 
{ 
    fin.open("numbers.txt"); 
    if (fin.fail()) 
    { 
     cout << "File failed to open"; 
     exit(1); 
    } 


    for(int i = 0; i < size; i++) 
    { 
     a[i] = 0; 
    } 

    cout << "The numbers in the array are: \n\n"; 

    for (int i = 0; i < size; i++) 
    { 
     if (!fin.eof()) 
     { 
      fin >> a[i]; 
      array_size ++; 
     } 
    } 

    for (int i = 0; i < array_size; i++) 
    { 
      cout << a[i] << " "; 
    } 

    cout << "\n\n\n"; 
    cout << "The numbers in the array sorted are: \n\n"; 

    for(int i = 0; i < array_size; ++i) 
    { 
     int temp2 = a[i]; 

     for (int j = i+1; j < array_size; ++j) 
     { 

      if(a[j] < temp2) 
      { 
       temp2 = a[j]; 

       int temp = a[i]; 
       a[i] = a[j]; 
       a[j] = temp; 
      } 
     } 
    } 





    for (int i = 0; i < array_size; i++) 
    { 
      cout << a[i] << " "; 
    } 

    cout << "\n\n\n"; 

    fin.close(); 
} 

Когда сделано, программа должна принять входные данные из файла, назначив его массиву, а затем отсортировать массив. После этого мне нужно использовать двоичный поиск, чтобы найти номер, заданный пользователем, и отобразить его место в массиве пользователю.

обновление: получение неправильного вывода для найденного индекса .... должен ли я просто добавить один для midindex?

void binary_search (int a[], int & array_size) 
{ 
    cout << "Please enter the element you would like to search for \n"; 
    int element; 
    cin >> element; 

    int lastindex=array_size-1, startindex=0; 

    while (startindex <= lastindex) 
    { 
     int midindex= startindex + (lastindex - startindex)/2; 

     if(element > a[midindex]) 
     { 
      startindex=midindex+1; 
     } 
     else if (element < a[midindex]) 
     { 
      lastindex=midindex-1; 
     } 
     else if (element == a[midindex]) 
     { 
      cout<<"Element "<<element<<" found at index "<<midindex<<endl; 
      return; 
     } 



    } 

} 

Answer 1

Try изменения

startindex=midindex; 

к:

startindex=midindex + 1; 

и

int midindex=(array_size/2); 

в

int midindex= startindex + (lastindex - startindex)/2 

и, самое главное, вы ничего не делаете, когда найдете элемент!

if(element == a[midindex]) { 
    cout<<"Element "<<element<<" found at index "<<midindex<<endl; 
    return; 
} 

Answer 2

Моя первая реакция, чтобы изменить линию

int midindex=(array_size/2); 

к

int midindex = startindex + (lastindex - startindex)/2; 

Кроме того, вы не хотите, чтобы сообщить, если искомый элемент найден или нет? Для того, чтобы обнаружить случай, когда обнаружен элемент, другая ветвь if как следующий

if(element == a[midindex]) 

может быть вставлена. Это может иметь return element; или return midindex внутри него в сочетании с return failure; вне цикла.

---

EDIT: Я сделал случайные попытки написать версию двоичного поиска. Я не утверждаю, что это правильно, поскольку бинарный поиск (in) известен тем, что он неверен. Some code with test cases and output загружается в кодекса.

Отрывок:

int * 
mybsearch(int const * const a, size_t const n, int const key) { 

    int * lo = const_cast< int * >(a); 
    int * hi = lo + n; 

    while(lo <= hi) { 

     int * const mid = lo + (hi - lo)/2; 
     int const midelem = *mid; 

     if(key == midelem) { 
      return mid; 
     } 
     else if(key < midelem) { 
      hi = mid - 1; 
     } 
     else { 
      lo = mid + 1; 
     } 
    } 

    return NULL; 
} 

Основной и тестовый код:

int main() { 

    int const arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90}; 
    size_t const num = sizeof(arr)/sizeof(int); 

    int * pos20 = mybsearch(arr, num, 20); 
    assert(pos20 && (*pos20 == 20)); 

    int * pos25 = mybsearch(arr, num, 25); 
    assert(!pos25); 

    int * pos5 = mybsearch(arr, num, 5); 
    assert(!pos5); 

    int * pos105 = mybsearch(arr, num, 105); 
    assert(!pos105); 
} 

Answer 3

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

Answer 4

Примите во внимание то, что не так в int midindex=(array_size/2);, когда array_size = 1. Затем обобщите на array_size = 3. Затем на любое нечетное число. Это потребует небольших симуляций в голове или на бумаге.

Answer 5

Вы близко. Вы хотите сделать что-то вроде этого:

int binary_search ... 

так что вы можете вернуть индекс элемента

while (startindex < lastindex)  
{ 
    int midindex=(startindex+endindex)/2; 
    if(element = a[midindex]) { 
     return midindex; 
    } 
    else if(element > a[midindex]) 
    { 
     startindex=midindex+1;