Я пытаюсь написать программу, которая сортирует массив размера N с помощью сортировки выборок, а затем выполняет двоичный поиск случайного числа в этом массиве и отображает индекс, в котором присутствует это число. Я заметил, что без моей функции двоичного поиска я начинаю получать переполнение стека, когда N больше, чем 1e5, и когда я пытаюсь запустить двоичный поиск, я сталкиваюсь с ошибкой «нарушение прав чтения». Я был бы очень признателен за любую помощь в этом, особенно учитывая, что мой N должен быть 1e6.
#define N 10
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//function prototypes
void selectionSort(int array[], size_t length);
void swap(int* elementPtr, int* element2Ptr);
void printPass(int array[], size_t length, unsigned int pass, size_t index);
size_t binarySearch(const int b[], int searchKey, size_t low, size_t high);
unsigned long long int counter = 0;
unsigned long long int counter2 = 0;
long long unsigned int counter3 = 0;
int main(void) {
int array[N];
srand(time(NULL));
for (size_t i = 0; i < N; i++) {
array[i] = rand() % 90 + 10; // give each element a value
}
/*
puts("Unsorted array:");
for (size_t i = 0; i < N; i++) { //print the array
printf("%d ", array[i]);
}
puts("{\n");
*/
selectionSort(array, N);
/*
puts("Sorted array:");
for (size_t i = 0; i < N; i++) { //print the array
printf("%d ", array[i]);
}
*/
printf("\nTotal amount of comparisons: %d\n", counter);
printf("Total amount of swaps: %d", counter2);
int value = rand() % N + 1;
int index = binarySearch(array, value, 0, N);
printf("\nThe amount of times the value was compared was: %d\n", counter3);
if (index != -1) {
printf("%d was first found on index %d\n", value, index);
}
else printf("%d was not found on the array\n", value);
}
void selectionSort(int array[], size_t length) {
//loop over length - 1 elements
for (size_t i = 0; i < length - 1; i++) {
size_t smallest = i; //first index of remaining array
//loop to find index of smallest element
for (size_t j = i + 1; j < length; j++) {
counter++;
if (array[j] < array[smallest]) {
smallest = j;
}
}
swap(array + i, array + smallest); //swap smallest element
//printPass(array, length, i + 1, smallest); //output pass
}
}
//function that swaps two elements in the array
void swap(int* elementPtr,int* element2Ptr)
{
counter2++;
int temp;
temp = *elementPtr;
*elementPtr = *element2Ptr;
*element2Ptr = temp;
}
//function that prints a pass of the algorithm
void printPass(int array[], size_t length, unsigned int pass, size_t index) {
printf("After pass %2d: ", pass);
//output elements till selected item
for (size_t i = 0; i < index; i++) {
printf("%d ", array[i]);
}
printf("%d ", array[index]); //indicate swap
//finish outputting array
for (size_t i = index + 1; i < length; i++) {
printf("%d ", array[i]);
}
printf("%s", "\n "); //for alignment
//indicate amount of array that is sorted
for (unsigned int i = 0; i < pass; i++) {
printf("%s", "-- ");
}
puts(""); //add newline
}
size_t binarySearch(const int b[], int searchKey, size_t low, size_t high) {
counter3++;
if (low > high) {
return -1;
}
size_t middle = (low + high) / 2;
if (searchKey == b[middle]) {
return middle;
}
else if (searchKey < b[middle]) {
return binarySearch(b, searchKey, low, middle - 1);
}
else {
return binarySearch(b, searchKey, middle + 1, high);
}
}