Example:
Array:
{5, 6, 7, 6, 5, 4, 3, 4, 5, 6}
Key:
4
Output:
The element 4 is found at the index 6.
Explanation:
We can solve this approach by traveling the matrix element one by one and searching for the element.
But we can have an optimized solution, as we know that the difference between the elements is 1.
We can follow the below steps:
Take the first element and subtract with the given key, you will get a value. Let’s store it in “diff” variable.
As we know that the array elements are having a difference of one, instead of searching once by one, we jump by diff and search for the element.
Solution Explanation:
{5, 6, 7, 6, 5, 4, 3, 4, 5, 6}
Pass 1: i=0 arr[0] is 5 == 4 No i = i + (5 - 4) i = 1
Pass 2: i = 1 arr[1] is 6 == 4 No i = i + (6 - 4) i = 3
Pass 3: i = 3 arr[3] is 6 == 4 No i = i + (6 - 4) i = 5
Pass 4: i =5 arr[5] is 4 == 4 Yes return i
Solution in C:
#include<stdio.h> #include<stdlib.h> int search_element(int arr[], int lenght, int key) { int diff; int itr = 0; while (itr < lenght) { if (arr[itr] == key) return itr; diff = abs(arr[itr] - key); itr += diff; } return -1; //element not found } int main() { int arr[100] = {5, 6, 7, 6, 5, 4, 3, 4, 5, 6}; int lenght = 10; int key = 4; int index = 0; index = search_element(arr, lenght, key); if(index >=0 ) printf("The key is found at index %d\n", (index + 1) ); else printf("Key not found\n"); return 0; }
Output:
The key is found at index 6
Vatsal Sonigara
Actually we can improve the search by making specific jumps.
For example if we are searching 5 and on the way we encounter a number 10 so we can skip next 4 places and directly move to the 5th position after the key 10 as there will be at least 4 places till we can reach the key 5.
Rohit Hegde
#include
#include
int main(){
int num_elements; //number of elements
int i; //temporary iterable variable
int key;
int key_pos = -1;
printf(“Enter the number of elements:\n”);
scanf(“%d”, &num_elements);
int arr_numbers[num_elements]; //to store the numbers
printf(“Enter the array elements:\n”);
for(i=0; i<num_elements; i++){
scanf("%d", &arr_numbers[i]);
}
/*
printf("Array elements:\n");
for(i=0; i<num_elements; i++){
printf("%d ", arr_numbers[i]);
}
*/
printf("Enter the key:\n");
scanf("%d", &key);
/*Now we are gonna iterate through the loop but…
the increment in 'i' will be equal to the difference between the current element and the key.
This is so because if current element is 10 and key is 12 then we are sure that
the key(12) won't be found in the next place as the next element should be either 11 or 9
according to the question. So we can skip the next element.
So the key, 12, can be found only in the 2nd place after 10 i.e. if the next element after 10 is 11
and the next element after 11 is 12. This is the best case.
So we are sure that the key, 12, won't be found in the next place and it can only be found, in best case,
in the 'p'th position after the current element, which is the difference between
the current element and the key to be searched.
*/
for(i=0; i<num_elements;){
//printf("Current element: %d\n", arr_numbers[i]);
if(arr_numbers[i] == key){
key_pos = i;
break;
}
//i++;
i = i + abs(arr_numbers[i]-key);
}
if(key_pos == -1)
printf("Not found\n");
else
printf("The position of key %d is: %d\n", key, i+1);
return 0;
}
Rahul
It can be solved with preprocessing O(n) and then each query O(1) using hashing. Consider there are n elements in the array. Let the first element be a.
Now the maximum element possible in the array is <= a + n, and minimum element possible is <= a – n. Now, we create an array of size 2 * n with its ith element denoting 1st index of element (a – n + i).
Now traverse the given array (hasharr) and fill the hash array for every element e as hasharr[e-a+n] = index.
Answer each query as:
index = hasharr[key – a + n]
Manas
in the given code if we search 7 it will not give answer
we need to add absolute difference in the index
prodevelopertutorial
Yes, will change the code accordingly. Thanks