Loop/Поиск по массиву до определенного индекса

Question

Как вы прокручиваете массив до тех пор, пока не достигнете последних 50 элементов вашего массива. Я хотел бы искать данный массив, пока не дойду до последних 50 элементов этого массива , то поиск завершается последовательным просмотром 50 элементов. Мой вопрос в том, как я могу построить такой цикл и как перейти к методу, который выполняет линейный поиск.

Скажем, у меня есть следующий код поиска Фибоначчи. он похож на двоичный поиск, за исключением того, что он использует следующее число Фибоначчи, чтобы разделить список на два параметра.

Фибоначчи Поиск Код:

public class Practice 
{ 
static int Fib[] = 
    { 
     0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 
     10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 
     5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 
    433494437, 701408733, 1134903170, 1836311903 
    }; 

static int binsrch_geq(int n, int val) 
{ 
    int low, high, mid; 
    int geq; 
    low = 0; 
    high = n - 1; 
    geq = -1; 
    while (low <= high) 
    { 
     mid = (low + high) >> 1; 
     if (val < Fib[mid]) 
     { 
      high = mid - 1; 
      geq = mid; 
     } 
     else if (val > Fib[mid]) 
     { 
      low = mid + 1; 
     } 
     else 
     { 
      return mid; 
     } 
    } 
    return geq; 
} 

static int fibsrch(int arr[], int n, int val) 
{ 
    int k, idx, offs; 
    int prevn = -1, prevk = -1; 
    if (n != prevn) 
    { 
     k = (n > 1) ? binsrch_geq(Fib.length, n) : 1; 
     prevk = k; 
     prevn = n; 
    } 
    else 
    { 
     k = prevk; 
    } 
    for (offs = 0; k > 0;) 
    { 
     idx = offs + Fib[--k]; 
     if (idx >= n || val < arr[idx]) 
     { 
      continue; 
     } 
     else if (val > arr[idx]) 
     { 
      offs = idx; 
      --k; 
     } 
     else 
     { 
      return idx; 
     } 
    } 
    return -1; 
} 

public static void main(String[] args) 
{ 
    int data[] = 
    { 
     1, 4, 5, 7, 9, 11, 13, 16, 18, 20, 25, 27, 30, 32, 33, 36, 39, 41, 44, 47, 51, 53, 55, 60,61,64,66,69,71,72, 
     74,75,79,80,81,83,87,88,90,92,94,95,96,97,98,99,100,101,105,106,109,111,112,119,120,122,124,126,129,130,134, 
     135,138,139,143,144,145,146,149,150,153,159,160,164,166,167 
    }; 
    int i, x, n; 

    /////////////////////////////////////// 
    /////////////////////////////////////// 
    x = 164; 
    ////////////////////////////////////// 
    ////////////////////////////////////// 
    n = data.length; 
    i = fibsrch(data, n, x); 
    if (i >= 0) 
    { 
     System.out.println(x + " found at index " + (i+1)); 
    } 
    else 
    { 
     System.out.println(x + " was not found"); 
    } 
} 

}

Answer 1

Если вы знаете, что массив имеет, по крайней мере, 50 элементов, вы можете написать:

//PRE: arr.length >= 50 
public int searchInTop50(int[] arr, int val){ 
    for(int i = arr.length - 50; i < arr.length; i++){ 
     if(a[i] == val) 
      return i; 
    } 
    return -1; 
} 

Она возвращает индекс стоимости если найдено, в противном случае -1. Его можно назвать как любой другой метод. Если я правильно понял ваш вопрос, вы можете выполнить двоичный поиск по первому n - 50 элементов, а затем, если значение не найдено, выполните метод searchInTop50. чтобы остановить поиск по определенному индексу, вы можете передать его аргументам двоичного метода поиска. Индексы start и stop обычно передаются в рекурсивную реализацию двоичного поиска. Вы можете посмотреть на это.