我正在嘗試創建一個函式，該函式回傳陣列中給定整數的最右邊位置的位置。示例：[1,2,3,4,5,6] 找到 4 的最右邊位置將回傳 4。 [1,2,3,4,4,4,5,6] 找到 4 的最右邊位置將回傳6.
我正在嘗試在我的函式中實作遞回呼叫。列印出遞回呼叫時，我看到了正確的位置，盡管我最終無法回傳該號碼。
#include <stdio.h>
int RightMostBinarySearch(int *arr, int length, int find, int i, int j) {
int middle = (i j) / 2; //This will be floor due to integer data type
while(i <= j){ //While the start does not excede int size of last value in array
if(arr[middle] < find){ //If middle element is less than what is being searched for
i = middle 1; //Obviously the element is not found and the element is greater than middle point => make i one element to the right
}
else if(arr[middle] == find){ //The middle position is where the element exists in the array
printf("%d\n", RightMostBinarySearch(arr, length, find, middle 1, j));
return middle 1;
}
else{ //This condition will be when arr[midd] > find
j = middle - 1; // make j 1 element left of middle because find is less than arr[middle]
}
middle = (i j) / 2; //if not found i or j changes, thus middle must also change.
}
return -1;
}
int main(void) {
int arr[] = { 1, 2, 4, 4, 4, 4, 4, 9, 12 }; //Sorted int array of size n
int find = 4;
int length = sizeof(arr) / sizeof(*arr); // Determines the length by getting the full size of memory array uses and dividing by he size of first element memory size. Full memory / element memory = num elements = length
int i = 0;
int j = length - 1; // Length of array is n, last element is represented n - 1
int location = RightMostBinarySearch(arr,length, find, i, j);
printf("The location of the element is at position: %d\n", location);
return 0;
}
uj5u.com熱心網友回復：
當函式RightMostBinarySearch遞回時，你列印它的回傳值，但總是 return middle 1，這甚至可能不是與find值出現的偏移量。
您應該這樣修改函式：
int RightMostBinarySearch(int *arr, int length, int find, int i, int j) {
//While the start does not exceed int size of last value in array
while (i <= j) {
// This will be floor due to integer data type
// Also avoid potential integer overflow in i j
// make sure the middle element is > i unless i == j
int middle = i (j - i 1) / 2;
//If middle element is less than what is being searched for
if (arr[middle] < find) {
//Obviously the element is not found and the element is greater than middle point => make i one element to the right
i = middle 1;
} else
if (arr[middle] == find) {
//The middle position is where the element exists in the array
if (middle == j) {
/* middle is the last possible value */
return middle;
} else {
return RightMostBinarySearch(arr, length, find, middle, j));
}
} else {
//This condition will be when arr[midd] > find
j = middle - 1; // make j 1 element left of middle because find is less than arr[middle]
}
}
return -1;
}
請注意，無需遞回函式，使用更簡單的 API 即可輕松解決此問題：
#include <stdio.h>
int LeftMostBinarySearch(const int *arr, int length, int find) {
int i = 0;
int j = length;
while (i < j) {
// compute mid-point avoiding potential overflow on i j
int middle = i (j - i) / 2;
if (arr[middle] < find) {
i = middle 1;
} else {
j = middle;
}
}
if (i < length && arr[i] == find)
return i;
else
return -1;
}
int RightMostBinarySearch(const int *arr, int length, int find) {
int i = 0;
int j = length;
while (i < j) {
// compute mid-point avoiding potential overflow on i j
int middle = i (j - i) / 2;
if (arr[middle] <= find) {
i = middle 1;
} else {
j = middle;
}
}
if (i > 0 && arr[i - 1] == find)
return i - 1;
else
return -1;
}
int main() {
int arr[] = { 1, 2, 4, 4, 4, 4, 4, 9, 12 }; //Sorted int array
int length = sizeof(arr) / sizeof(*arr); // Determines the length by getting the full size of memory array and dividing by the size of first element. Full memory / element memory = num elements = length
int find = 4;
int left_location = LeftMostBinarySearch(arr, length, find);
int right_location = RightMostBinarySearch(arr, length, find);
printf("The first element %d is at position: %d\n", find, left_location);
printf("The last element %d is at position: %d\n", find, right_location);
return 0;
}
uj5u.com熱心網友回復：
if you are using recursion, I don't think you'd need the while loop?
Here is how I think you can arrive at the solution for this problem. You should return for every step as I see put.
int rmst(int *arr, int length, int find, int i, int j){
if (i <= j) {
int middle = (i j)/2;
if (arr[middle] < find){
return rmst(arr, length, find, middle 1, j);
} else if (arr[middle] == find){
if ((middle 1) < length){
if (arr[middle 1] == find){ // continue binary search if the next guy is still == find, otherwise, return middle.
return rmst(arr, length,find, middle 1, j);
}
}
return middle;
} else {
return rmst(arr, length, find, i, middle -1);
}
}
return -1;
}
uj5u.com熱心網友回復：
Firstly indices in arrays in C start from 0.
Secondly the value of the parameter length is not used in your function.
Thirdly if the first if condition evaluates to true then in fact you have not a recursive function. You have an iterative function with a while loop.
while(i <= j){ //While the start does not excede int size of last value in array
if(arr[middle] < find){ //If middle element is less than what is being searched for
i = middle 1; //Obviously the element is not found and the element is greater than middle point => make i one element to the right
}
//...
middle = (i j) / 2; //if not found i or j changes, thus middle must also change.
}
So when the value of the variable find is greater than any element of the array you have a fully iterative function.
When this if statement
else if(arr[middle] == find){ //The middle position is where the element exists in the array
printf("%d\n", RightMostBinarySearch(arr, length, find, middle 1, j));
return middle 1;
}
evaluates to true then this call
RightMostBinarySearch(arr, length, find, middle 1, j)
has no effect and the function returns the value of middle 1 independent on whether indeed arr[middle 1] is equal to find.
The function has too many parameters.
And at last the parameter that specifiers the array shall have the qualifier const because the array itself is not being changed within the function.
The function can be declared and defined the following way as it is shown in the demonstration program below.
#include <stdio.h>
size_t RightMostBinarySearch( const int *a, size_t n, int value )
{
if (n == 0)
{
return -1;
}
else if ( value < a[n / 2] )
{
return RightMostBinarySearch( a, n / 2, value );
}
else if ( a[n / 2] < value )
{
size_t result = RightMostBinarySearch( a 1 n / 2, n - 1 - n / 2, value );
return result == -1 ? result : result 1 n / 2;
}
else
{
size_t result = RightMostBinarySearch( a 1 n / 2, n - 1 - n / 2, value );
return result == -1 ? n / 2 : result 1 n / 2;
}
}
int main( void )
{
int a1[] = { 1, 2, 3, 4, 5, 6 };
const size_t N1 = sizeof( a1 ) / sizeof( *a1 );
printf( "%zu\n", RightMostBinarySearch( a1, N1, 4 ) );
int a2[] = { 1, 2, 3, 4, 4, 4, 5, 6 };
const size_t N2 = sizeof( a2 ) / sizeof( *a2 );
printf( "%zu\n", RightMostBinarySearch( a2, N2, 4 ) );
}
The program output is
3
5
As you can see neither while statement or any other loop is present in the recursive function.
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/451557.html