排序數組中的遞歸二進制搜索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個變量可用。 （最小和最大） 但我只有三個，有沒有辦法編輯數組的起始點給予下一個函數？

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 

第n個元素的地址是大小尺寸爲N的數組

Answer 3

假設你有你的四PARAM版本：

find(value, array, min, max); 

與三參數版本，你可以撥打：

find(value, array + min, max); 

請注意，max排列的第th個元素實際上是的array + min 10個元素，所以要根據您的實現可能需要調用

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); 
    } 
}