Рекурсивный двоичный поиск в отсортированном массиве C++

Question

Мне нужно написать рекурсивную функцию, которая ищет через отсортированный массив.

#include <iostream> 
using namespace std; 

int find(int value, int* folge, int max) { 

} 


int main() { 
    int const n = 7; 
    int wert1 = 4, wert2 = 13, wert3 = 2, wert4 = 25; 
    int folge[n] = {3,4,9,13,13,17,22}; 
    wert1 = find(wert1, folge, n); 
} 

Это часть кода, который был предоставлен нам, и мы должны его закончить.
Я знаю, как это сделать, если у вас есть 4 переменные. (min и max) Но у меня только три, есть ли способ редактировать начальную точку массива, которая присваивается следующей функции?

Answer 1

Функция может быть записана следующим образом

#include <iostream> 

int find(int value, int* folge, int max) 
{ 
    if (max == 0) return -1; 

    int middle = max/2; 

    if (folge[middle] == value) return middle; 

    bool lower = value < folge[middle]; 
    int n = lower ? find(value, folge, middle) 
        : find(value, folge + middle + 1, max - middle - 1); 

    return n != -1 && !lower ? n + middle + 1: n; 
} 

int main() 
{ 
    int const n = 7; 
    int wert1 = 4, wert2 = 13, wert3 = 2, wert4 = 25; 
    int folge[n] = {3,4,9,13,13,17,22}; 

    std::cout << wert1 << " = " << find(wert1, folge, n) << std::endl; 
    std::cout << wert2 << " = " << find(wert2, folge, n) << std::endl; 
    std::cout << wert3 << " = " << find(wert3, folge, n) << std::endl; 
    std::cout << wert4 << " = " << find(wert4, folge, n) << std::endl; 

    return 0; 
} 

Выход программы

4 = 1 
13 = 3 
2 = -1 
25 = -1 

Или еще одна тестовая программа

#include <iostream> 

int find(int value, int* folge, int max) 
{ 
    if (max == 0) return -1; 

    int middle = max/2; 

    if (folge[middle] == value) return middle; 

    bool lower = value < folge[middle]; 
    int n = lower ? find(value, folge, middle) 
            : find(value, folge + middle + 1, max - middle - 1); 

    return n != -1 && !lower ? n + middle + 1: n; 
} 

int main() 
{ 
    int const n = 7; 
    int folge[n] = {3,4,9,13,13,17,22}; 

    for (int x : { 2, 3, 4, 9, 13, 17, 22, 25 }) 
    { 
     std::cout << x << " -> " << find(x , folge, n) << std::endl; 
    }   

    return 0; 
} 

Его выход

2 -> -1 
3 -> 0 
4 -> 1 
9 -> 2 
13 -> 3 
17 -> 5 
22 -> 6 
25 -> -1 

Answer 2

find(&folge[1],...) // ignore first element 

Адрес п-го элемента представляет собой массив размера Размер-н

Answer 3

Предположим, у вас есть свой вариант четыре-парам:

find(value, array, min, max); 

с версией три параметра вы можете позвонить:

find(value, array + min, max); 

Обратите внимание, что max «го элемента массива фактически max-min-й элемент array + min, поэтому в зависимости от реализации вы можете позвонить

find(value, array + min, max - min); 

Answer 4

Вы можете изменить значение указателя INT folge

int find(int value, int* folge, int max) { 
    if (max == 0) { 
     return -1; 
    } 

    int mid=max/2; 

    if (value == folge[mid]) 
    { 
     return mid; 
    } 

    int base=0; 

    if (value < folge[mid]) 
    { 
     max=mid-1; 
    } 
    else 
    { 
     max-=(mid+1); 
     base=mid+1; 
    } 

    int ret=find(value,folge+base,max); 

    if (ret == -1) 
    { 
     return -1; 
    } 

    return ret+base; 
} 

Answer 5

Если folge указывает на первый элемент, то folge+1 будет указывать на второе.

int find(int value, int* folge, int max) 
{ 
    int m = max/2; 
    if (0 == max) 
    { 
     return -1; 
    } 

    if (value == folge[m]) 
    { 
     return value; 
    } 
    else if (value < folge[m]) 
    { 
     return find(value, folge, m); 
    } else 
    { 
     return find(value, folge + m + 1, max - m - 1); 
    } 
}