Write a function that performs a binary search for the location of a new element in an ordered array and returns a pointer to the location of the inclusion of a new element. Using this function to implement sorting inserts. I wrote the code, but I don’t know how to consider if my element is more than the last element in the array or less. And in general, I'm not sure that the code works correctly, because I work with pointers for the first time. Help to understand, please.

#include<iostream> using namespace std; int search(int* array, int len, int n){ ////СОРТИРОВКА ВСТАВКАМИ for (int i = 0; i < len; i++){ int temp = array[0]; for (int j = i + 1; j < len; j++){ if (array[i] > array[j]){ temp = array[i]; array[i] = array[j]; array[j] = temp; } } } ////БИНАРНЫЙ ПОИСК int *ptr = 0; int l = 0, r = len - 1 ; while(r>l){ int mid = (l + r)/2; if(n<=array[mid]) r = mid; else l = mid +1; }if(array[l] == n) ptr = &l; if(array[l] < n){ int a = l-1; ptr = &a; }if(array[l] > n) ptr = &l ; return *ptr; } int main(){ setlocale(LC_ALL, "rus"); int size,n; cout << "Введите размер массива: "; cin >> size; cout << "Введите цифру: "; cin >> n; int* mas = new int[size]; for(int i = 0; i<size; i++) cin >> mas[i]; search(mas, size, n); int res = search(mas, size, n); for(int i = 0;i<size; i++) cout<<mas[i]<<" "; cout<<"Элемент должен стоять на позиции между "<< res << " и " << res + 1<<" элементом "<< endl; delete []mas; return 0; }

    2 answers 2

    You apparently did not understand the essence of the problem. You need to implement sorting inserts , but not in the academic version, as you have under the comment "//// SORT BY INSERTS". And so that a binary search would be used to search for the insertion point. Look here:

    enter image description here

    The black boxes show the elements of the sorted part of the array. As you can see, the sorted part is always at the beginning, while it is known where it ends. We successively compare neighboring elements, if the next element is less than the previous one, then it moves to the correct place of the sorted part. Here you need to apply a binary search to search for this right place.

    By the way, it is worth noting that in the implementation with a binary search, sorting inserts has a worse performance than in academic.

    Yes, here's another:

     int l = 0, r = len - 1 ; while(r>l) { int mid = (r - l)/2; // а не (l + r)/2; if(n <= array[mid]) r = mid; else l = mid + 1; } //... if(array[l] < n) { int a = l-1; ptr = &a; // берется указатель на локальную переменную! }
    • Another thing to say, the use of binpros in this algorithm is absolutely meaningless and only degrades performance. - Qwertiy ♦
    • you can write a binary search, and then on Vicky only in pseudocode - Asya Filatova
    • 2
      @ AsyaFilatova But this is not funny anymore. - Cerbo
    • @Cerbo Okay, ok, don't worry, I'll figure it out myself) - Asya Filatova
    • @Qwertiy Thank you - Cerbo

    First, if you need a pointer, then change the return type to a pointer: int* .

    Then, l and r are local variables in the function, they will die after the function ends, their memory will be given to someone else, and the pointer will indicate to whom God will send. It is not right. You must return a pointer to an element of the array, because the array will survive the end of the function. For example, if you want to return a pointer to array[l] , return &array[l] .

    Dare!