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 travelling 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 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>
int search_element(int arr[], int lenght, int key)
{
int diff;
int itr = 0;
while (itr < lenght)
{
if (arr[itr] == key)
return itr;
diff = 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