英文:
How to output left and right block indexes in JumpSearch in Java?
问题
我在尝试输出在_jump search_算法中块的左右索引，但我真的不知道如何做。你有任何想法吗？最后一个块可能会更短，所以左边界可能会比其他的要短，所以我无法真正想象出一个解决方案。当我声明一个新变量并在循环中尝试更新它时，在循环外部它仍然保持旧值，我真的不知道为什么。
我的代码：
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int length = scanner.nextInt();
int[] array = new int[length];
for (int i = 0; i < array.length; i++) {
array[i] = scanner.nextInt();
}
int target = scanner.nextInt();
jumpSearch(array,target);
}
public static int jumpSearch(int[] array, int target) {
int currentRight = 0;
int prevRight = 0;
// 如果数组为空，则元素未找到
if (array.length == 0) {
return -1;
}
// 检查第一个元素
if (array[currentRight] == target) {
return 0;
}
// 计算数组元素的跳跃长度
int jumpLength = (int) Math.sqrt(array.length);
// 找到可能包含目标元素的块
while (currentRight < array.length - 1) {
// 计算下一个块的右边界
currentRight = Math.min(array.length - 1, currentRight + jumpLength);
if (array[currentRight] >= target) {
break; // 找到可能包含目标元素的块
}
}
prevRight = currentRight; // 更新前一个右边块的边界
// 如果到达了最后一个块，并且它不能包含目标值 => 未找到
if ((currentRight == array.length - 1) && target > array[currentRight]) {
return -1;
}
/* 在找到的块中进行线性搜索 */
// backwardSearch(array, target, prevRight, currentRight);
return 0;
}
public static int backwardSearch(int[] array, int target, int leftExcl, int rightIncl) {
for (int i = rightIncl; i > leftExcl; i--) {
if (array[i] == target) {
return i;
}
}
return -1;
}
}
英文:
I'm trying to output left and right indexes of the block in jump search algorithm, but I don't really know how to do it. Do you have any idea? The last block may be shorter so probably left border is going to be shorter than the others, so I can really picture a solution. When I'm declaring a new variable and I'm trying to update it in a loop, then outside of the loop it still has the old value and I really don't know why.
My code:
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int length = scanner.nextInt();
int[] array = new int[length];
for (int i = 0; i < array.length; i++) {
array[i] = scanner.nextInt();
}
int target = scanner.nextInt();
jumpSearch(array,target);
}
public static int jumpSearch(int[] array, int target) {
int currentRight = 0;
int prevRight = 0;
// If array is empty, the element is not found
if (array.length == 0) {
return -1;
}
// Check the first element
if (array[currentRight] == target) {
return 0;
}
// Calculating the jump length over array elements
int jumpLength = (int) Math.sqrt(array.length);
// Finding a block where the element may be present
while (currentRight < array.length - 1) {
// Calculating the right border of the following block
currentRight = Math.min(array.length - 1, currentRight + jumpLength);
if (array[currentRight] >= target) {
break; // Found a block that may contain the target element
}
prevRight = currentRight; // update the previous right block border
// If the last block is reached and it cannot contain the target value => not found
if ((currentRight == array.length - 1) && target > array[currentRight]) {
return -1;
}
/* Doing linear search in the found block */
// backwardSearch(array, target, prevRight, currentRight);
return 0;
}
public static int backwardSearch(int[] array, int target, int leftExcl, int rightIncl) {
for (int i = rightIncl; i > leftExcl; i--) {
if (array[i] == target) {
return i;
}
}
return -1;
}
}
答案1
得分: 0
以下是您要求的代码翻译部分：
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;
// 找到要跳跃的块大小
int step = (int)Math.floor(Math.sqrt(n));
// 找到元素所在的块（如果存在）
int prev = 0;
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
// 在以prev为开头的块中进行线性搜索
int left = prev; // 添加了这一行
int right = Math.min(step, n); // 添加了这一行
while (arr[prev] < x)
{
prev++;
// 如果达到下一个块或数组末尾，则元素不存在。
if (prev == Math.min(step, n))
return -1;
}
// 如果找到元素
if (arr[prev] == x) {
System.out.printf("在%d和%d之间找到%d%n", left, right, x); // 添加了这一行
return prev;
}
return -1;
}
// 测试函数
public static void main(String [ ] args)
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610};
int x = 55;
// 使用Jump Search查找'x'的索引
int index = jumpSearch(arr, x);
// 打印'x'所在的索引
System.out.println("\n数字 " + x +
" 在索引 " + index);
}
}
当我运行上述代码时，我得到以下输出：
在8和12之间找到55
数字55在索引10
这是否是您要寻找的内容？
<details>
<summary>英文:</summary>
Here is the code from the example that I linked to in my comment to your question. I added three lines to it. I added a the following comment to each line I added.
// ADDED THIS LINE
-----------
```java
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;
// Finding block size to be jumped
int step = (int)Math.floor(Math.sqrt(n));
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
int left = prev; // ADDED THIS LINE
int right = Math.min(step, n); // ADDED THIS LINE
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == Math.min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x) {
System.out.printf("Found %d between %d and %d%n", x, left, right); // ADDED THIS LINE
return prev;
}
return -1;
}
// Driver program to test function
public static void main(String [ ] args)
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610};
int x = 55;
// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x);
// Print the index where 'x' is located
System.out.println("\nNumber " + x +
" is at index " + index);
}
}
When I run the above code, I get this output.
<!-- language: lang-none -->
Found 55 between 8 and 12
Number 55 is at index 10
Is that what you are looking for?
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论