我正在尝试创建一个函数，该函数返回数组中给定整数的最右边位置的位置。示例：[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;
}
当函数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;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句