alalba Ответов: 3

Задача рекурсивного алгоритма для выполнения двоичного поиска в отсортированном массиве

Я хочу внедрить алгоритм двоичного поиска массива ордеров.
int Array::Search(int target, int* start, int* tail){
	if(start>tail){
		cout<<"not find"<<endl;
		return -1;
	}
	int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
	cout<<"offset: "<<offsetMid<<"  mid " <<*(start+offsetMid)<<endl;
	cout<<start<<" " <<tail<<endl;
	if(target == *(start+offsetMid) ){
		cout<<"mid"<<endl;
		return (offsetMid+1);
	}
	if(*(start+offsetMid) > target){
		cout<<"left"<<endl;
		tail = start+(offsetMid-1)*sizeof(int);
		return Search(target, start, tail);
	}
	if(*(start+offsetMid) < target){
		cout<<"right"<<endl;
		start = start+(offsetMid)*sizeof(int);
		return Search(target,start , tail);
	}
}

Но это не работает, я знаю, что параметр func лучше должен быть индексом массива, а не указателем, я просто хочу попробовать этот способ. Компилятор, который я использовал, это 
gcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC)
Еще одна странная вещь 
int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
И tail, и start имеют тип int*, но разница между ними подсчитывается байтом, поэтому я должен разделить ее на sizeof(int), чтобы получить значение смещения.
if(*(start+offsetMid) > target)
Но когда я хочу добавить значение смещения к стартовому адресу, чтобы получить значение в определенной позиции, я не должен определять время по sizeof(int).?

Что я уже пробовал:

Я попытался напечатать адреса как начальной, так и конечной точек, а также значение элемента в средней позиции.

3 Ответов

Рейтинг:
23

Midi_Mick

Проблему я вижу ты поправляешь свою указатели на sizeof(тип int). Поскольку они уже объявлены как указатели int, любые добавления или вычитания к указателям корректируются компилятором sizeof(int).
т.е.

int* pi = //a valid pointer;
void* pv = (void*)pi;

bool bAdj = (pi + 1) == (pv + sizeof(int)); // returns true
И tail, и start имеют тип int*, но разница между ними подсчитывается байтом, поэтому я должен разделить ее на sizeof(int), чтобы получить значение смещения.
Ошибаешься!! Это определяется языком (не имеет значения, какой компилятор вы используете). Вычитание этих двух указателей вернет число int, которое будет вписываться здесь.

alalba

Сначала я тоже думал, что это похоже на u, пока не столкнулся с этой проблемой. Во-первых, если я не настрою указатель на sizeof(int), то длина массива, который я получил для выражения (tail-start), будет в 4 раза больше, чем на самом деле. Во-вторых, если я использую значение в моем коде "инт offsetMid= (хвост-начало)/2/оператор sizeof(тип int);//на единицу инт" без скорректирована на sizeof(тип int), стоимость *(старт + offsetMid) получите мне значение, которое не существует в массиве,потому что offsetMid в 4 раза больше, чем она должна быть

Stefan_Lang

+5 вы действительно правы.
Я добавил Больше информации, чтобы помочь ОП в качестве отдельного решения. Я бы опубликовал это в качестве комментария здесь, но я предпочел преимущество форматирования кода.

Рейтинг:
2

Stefan_Lang

tl;dr:
возможно, вы захотите проверить свой тестовый код, вызывающий функцию поиска, - возможно, ошибка тоже есть!

Длинная версия:

Это не отдельное решение, а просто проверка решения 1. Я использую форму решения только для форматирования кода:

Используя этот тестовый код, я мог бы проверить правильность решения 1:

#include <iostream>
using std::cout;
using std::endl;

int Search(int target, int* start, int* tail){
   if(start>tail){
      cout<<"not find"<<endl;
      return -1;
   }
   int offsetMid= (tail-start)/2/*/sizeof(int)*/;//by unit of int
   cout<<"offset: "<<offsetMid<<"  mid " <<*(start+offsetMid)<<endl;
   cout<<start<<" " <<tail<<endl;
   if(target == *(start+offsetMid) ){
      cout<<"mid"<<endl;
      return (offsetMid+1);
   }
   if(*(start+offsetMid) > target){
      cout<<"left"<<endl;
      tail = start+(offsetMid-1)/**sizeof(int)*/;
      return Search(target, start, tail);
   }
   if(*(start+offsetMid) < target){
      cout<<"right"<<endl;
      start = start+(offsetMid)/**sizeof(int)*/;
      return Search(target,start , tail);
   }
}
void test_Search() {
   int arr[] = {2, 5, 6, 14, 44, 51, 94, 221, 356, 444};
   int* start = arr;
   size_t length = sizeof(arr)/sizeof(int);
   cout << length << endl;
   int *end = start + length;
   int s = Search(6, start, end);
   cout << s << endl;
}

Это приводит к выходу:
10
offset: 5  mid 51
0033FA60 0033FA88
left
offset: 2  mid 6
0033FA60 0033FA70
mid
3

Обратите внимание, как в тестовой функции я вычислил конечный адрес массива, явно разделив размер массива на sizeof(int) Это необходимо, потому что добавление числа к int указатель imlpicitely умножает смещение адреса на sizeof(int): Подозреваю, что это может быть причиной того, что вы не смогли воспроизвести ожидаемые результаты, следуя совету из решения 1.

P.S.: компилятор пожаловался со следующим предупреждением, которое я не потрудился исправить - но вы должны:
Цитата:
предупреждение C4715: 'Search' : не все пути управления возвращают значение

Это достаточно легко обнаружить, но если вы этого не сделаете, вот вам совет: что произойдет, если вы будете искать в приведенном выше массиве, скажем, значение 11?

Midi_Mick

Прекрасный пример.

Рейтинг:
15

Patrice T

Когда вы не понимаете, что делает ваш код или почему он делает то, что делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Он позволяет вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения, это невероятный инструмент обучения.

Отладчик-Википедия, свободная энциклопедия[^]

Отладчик здесь для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.

alalba

спасибо за совет, я постараюсь научиться пользоваться отладчиком.