Blog

Articles to grow your career

Article

A fairly common task is to find an element in an array. Let’s say we have an array `1,5,8,10,16,20... 100`

and we need to find the position of element 10 in it. Or even find out if there is such an element in the array.

There are the following algorithms to solve this problem:

- Linear search – О(n)
- Binary search – O(log (N))
- Jump search – O(sqrt (N))
- Interpolation search – O(log log N)
- Exponential search – O(log (N))

The simplest, but also the longest algorithm. Iterate over the elements of the array and compare with the `elementToSearch`

we need to find.

```
public static int linearSearch(int[] array, int elementToSearch) {
for (int i = 0; i < array.length; i++) {
if (array[i] == elementToSearch) {
return i;
}
}
return -1;
}
```

To use the algorithm, the array must be sorted. The idea of the method is that we divide the array in half, take the “middle element” with the `middleIndex`

index, and compare it with the one we are looking for. If they are equal, we end the search. If the desired element is less than the “middle element” we discard the right side of the array, otherwise – the left. Then we repeat these operations again and again until the desired element is found, or until the new segment becomes empty. If the element is not found, `return -1`

.

```
public static int binarySearch(int[] array, int elementToSearch) {
int firstIndex = 0;
int lastIndex = array.length - 1;
// conditions to stop the loop (element is not present)
while (firstIndex <= lastIndex) {
int middleIndex = (firstIndex + lastIndex) / 2;
// if average element - our targeted element, return the index
if (array[middleIndex] == elementToSearch) {
return middleIndex;
}
// if average element - less than
// we route our index to middle+1, removing the first part
else if (array[middleIndex] < elementToSearch) { firstIndex = middleIndex + 1; } // if average element - greater then // we route our index to middle-1, removing the second part else if (array[middleIndex] > elementToSearch) {
lastIndex = middleIndex - 1;
}
}
return -1;
}
```

```
public static int recursiveBinarySearch(int[] array, int firstElement, int lastElement, int elementToSearch) {
// conditions to stop
if (lastElement >= firstElement) {
int middle = (lastElement + firstElement) / 2;
// if average element - our targeted element, return the index
if (array[middle] == elementToSearch) {
return middle;
}
// if average element - greater then the targeted one
// call the recursion method
if (array[middle] > elementToSearch) {
return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch);
}
// call the recursion method
return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch);
}
return -1;
}
```

```
public static int jumpSearch(int[] array, int elementToSearch) {
int arrayLength = array.length;
int jumpStep = (int) Math.sqrt(array.length);
int previousStep = 0;
while (array[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) { previousStep = jumpStep; jumpStep += (int) (Math.sqrt(arrayLength)); if (previousStep >= arrayLength) {
return -1;
}
}
while (array[previousStep] < elementToSearch) {
previousStep++;
if (previousStep == Math.min(jumpStep, arrayLength)) {
return -1;
}
}
if (array[previousStep] == elementToSearch) {
return previousStep;
}
return -1;
}
```

Coding tasks for interviews