Двоичный поиск в массиве
Индексы должны быть целыми. Можно попробовать:
train_size = int(len(all_x)*0.7)
valid_size = int(len(all_x)*0.2)
test_size = int(len(x_prime)*0.1)
2 ответа
Удостоверьтесь, что Ваш массив отсортирован, так как это - затруднение двоичного поиска.
Любая индексируемая структура данных / структура данных произвольного доступа могут быть двоичные искавший. Таким образом, когда Вы говорите использование "просто массив", я сказал бы, что массивы являются самой основной структурой / структурой общих данных, на которой используется двоичный поиск.
можно сделать это рекурсивно (самый легкий) или многократно. Временная сложность двоичного поиска является O (зарегистрируйте N), который значительно быстрее, чем линейный поиск проверки каждого элемента в O (N). Вот некоторые примеры от Википедия: Алгоритм Двоичного поиска :
Рекурсивный:
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = low + ((high - low) / 2)
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
Повторяющийся:
BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = low + ((high - low) / 2)
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}
Единственная версия сравнения быстра и краткая
int bsearch_double(const double a[], int n, double v) {
int low = 0, mid;
while (n - low > 1) {
mid = low + (n - low) / 2;
if (v < a[mid]) n = mid;
else low = mid;
}
return (low < n && a[low] == v) ? low : -1;
}