Input: SORTED array, target

Output: element_index or -1 if is not present in array

Complexity:

step == 1 → $O(n)$ (linear search)

step == n → subsearch complexity

step ≠ 1 && step ≠ n → $\begin{cases} O(\frac{n}{step}+step), & \text{if subsearch is linear search} \\ O(\frac{n}{step}+\log{step}), & \text{if subsearch is binary search} \end{cases}$

Algorithm:

<aside> ⚙️

Псевдокод, где ещё требуется реализовать проверку, не перепрыгнули ли конец

#define STEP 2 // you can choose step whatever you want
if (target == array[0]) {
	printf(0); 
	exit(); 
}
if (target < array[0]) {
	printf("No such element in array\\n"); 
	exit(); 
}
if (target > array[0]) {
	int i = 1; 
	while (i < n) {
		if (target == array[0+i*STEP]) {
			printf(i*STEP); 
			exit(); 
		}
		if (target < array[0+i*STEP]) {
			subsearch(array[(i-1)*STEP: i*STEP], target); 
			exit(); 
		}
		if (target > array[0+i*STEP]) {
			i++; 
      // ещё должна быть проверка, не перепрыгнули ли конец
		}
	}
}

Псевдокод с реализованной проверкой на выход за границу массива и улучшенными границами subsearch:

#define STEP 2 // you can choose step whatever you want
if (target == array[0]) {
	printf(0); 
	exit(); 
}
if (target < array[0]) {
	printf("No such element in array\\n"); 
	exit(); 
}
while (i*step <= n) {
    if (target == array[0+i*STEP]) {
      printf(i*step); 
      exit(); 
    }
    if (target < array[0+i*STEP]) {
      subsearch(array[(i-1)*STEP+1 : i*STEP-1], target); 
      // + и - 1 т.к. i*STEPи (i-1)*step мы уже проверяли на совпадение с target
      exit(); 
    }
    if (target > array[0+i*step]) {
      i++; 
    }
  }
  subsearch(array[(i-1)*STEP+1 : n-1], target); 
  // если i*STEP выходит за размер массива и при этом меньше, чем target

</aside>