Searching for an element in the array – Algorithms for interview

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))

1. Linear search

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;
}

2. Binary search. Iterative approach.

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;
    }

3.

Contact

Do you want to join us?

Leave an application and get a free consultation from our manager.

• Help in choosing a direction
• Course consultation
• Additional materials for the start

Send

Binary search. Recursion approach.

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;
  }

4. Jump search.

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;
}