英文:
Fixed Point (Value equal to index) in a given array - 1 indexed using binary search
问题
可以修改这段代码，使索引值从1开始，而不是从0开始吗？
所以，如果数组是0 1 3 4，程序将返回3。
class Main
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
/* low + (high - low)/2; */
int mid = (low + high)/2;
if((mid + 1) == arr[mid]) // 修改此行，将mid改为mid+1
return mid + 1;
if((mid + 1) > arr[mid]) // 修改此行，将mid改为mid+1
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* 如果没有固定点，返回-1 */
return -1;
}
// 主函数
public static void main(String args[])
{
int arr[] = {-10, -1, 0, 3 , 10, 11, 30, 50, 100};
int n = arr.length;
System.out.println("固定点是 "
+ binarySearch(arr,0, n-1));
}
}
英文:
Is it possible to modify this code so that the index value starts from 1, instead of 0?
So, if the array is 0 1 3 4, the program will return 3.
class Main
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
/* low + (high - low)/2; */
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* Return -1 if there is
no Fixed Point */
return -1;
}
//main function
public static void main(String args[])
{
int arr[] = {-10, -1, 0, 3 , 10, 11, 30, 50, 100};
int n = arr.length;
System.out.println("Fixed Point is "
+ binarySearch(arr,0, n-1));
}
}
答案1
得分: 1
只需在调用 binarySearch 时将 0 更改为 1，将 n-1 更改为 n，并在 arr 的索引 0 处添加一个随机数，即按如下方式操作：
int arr[] = {99999999/*注意这个随机大数*/, -10, -1, 0, 4/*注意这个4*/ , 10, 11, 30, 50, 100};
和
binarySearch(arr, 1, n);
一个带有证明的完整示例：
public class SOTest
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
/* low + (high - low)/2; */
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* 如果没有固定点，则返回 -1 */
return -1;
}
//主函数
public static void main(String args[])
{
int arr[] = {99999999/*一些非常正数*/, -10, -1, 0, 4/*注意这个4*/, 10, 11, 30, 50, 100};
int n = arr.length;
System.out.println("Fixed Point is "
+ binarySearch(arr, 1, n));
}
}
输出：
Fixed Point is 4
英文:
just change the 0 to 1 and n-1 to n when calling binarySearch and add a random number at 0 index of arr, i.e. do as follows:
int arr[] = {99999999/*note this random large number*/, -10, -1, 0, 4/*note this 4*/ , 10, 11, 30, 50, 100};
and
binarySearch(arr, 1, n);
A full example with proof:
public class SOTest
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
/* low + (high - low)/2; */
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* Return -1 if there is
no Fixed Point */
return -1;
}
//main function
public static void main(String args[])
{
int arr[] = {99999999/*some very positive value*/, -10, -1, 0, 4/*note this 4*/, 10, 11, 30, 50, 100};
int n = arr.length;
System.out.println("Fixed Point is "
+ binarySearch(arr, 1, n));
}
}
output:
Fixed Point is 4
答案2
得分: 1
你可以将二分搜索中的 mid 替换为 (mid+1)。
class Main
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
/* low + (high - low)/2; */
int mid = low+(high-low)/2;
if((mid+1) == arr[mid])
return mid+1;
if((mid+1) > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* 如果没有固定点，则返回 -1 */
return -1;
}
// 主函数
public static void main(String args[])
{
int arr[] = {0,1,3,4};
int n = arr.length;
System.out.println("Fixed Point is "
+ binarySearch(arr,0, n-1));
}
}
输入:
arr = {0,1,3,4}
输出:
Fixed Point is 3
英文:
You can change your binary search replacing mid with (mid+1).
class Main
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
/* low + (high - low)/2; */
int mid = low+(high-low)/2;
if((mid+1) == arr[mid])
return mid+1;
if((mid+1) > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* Return -1 if there is
no Fixed Point */
return -1;
}
//main function
public static void main(String args[])
{
int arr[] = {0,1,3,4};
int n = arr.length;
System.out.println("Fixed Point is "
+ binarySearch(arr,0, n-1));
}
}
Input:
> arr = {0,1,3,4}
Output:
> Fixed Point is 3
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论