How to search in a nearly sorted array

Problem statement

Let’s suppose that you’re given a sorted array arr and a target value. Your goal is to determine the location of the target value in the array.

Certain elements are shifted to either of the adjacent indexes after the array was sorted, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Basically, the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].

Examples

Input Output
Example 1 arr = [15, 20, 30, 25, 35]
target = 25		 25 found at index 3
Example 2 arr = [15, 20, 30, 25, 35]
target = 100		 100 not found

Solution approach 1

A linear search is the simplest solution that can be applied to both sorted and unsorted data. The algorithm is as follows:

  1. Start from the first element of the array.
  2. Compare every element of the array with the target element.
    1. If the target element is equal to the array element, then return the index.
    2. If the target element is not equal to the array element, then move to the next element and repeat this step.
  3. If there are no more elements left in the array, you can conclude that the target element is not present in the array.

The time complexity of the algorithm is O(n) because every element of the array is compared in the worst case.

The space complexity of the algorithm is O(1) because no extra space is used.

Linear Search
1 of 5

Code

In the code below, the array is hard coded to [15, 20, 30, 25, 35]. Enter an integer value to be searched in the array.

import java.util.Scanner;
public class LinearSearchNearlySortedArray {
    private static int linearSearchNearlySorted(int[] arr, int target){
        for(int i=0;i < arr.length; i++){
            if(arr[i] == target) return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[]{15, 20, 30, 25, 35};
        int target = scanner.nextInt();
        int index = linearSearchNearlySorted(arr, target);
        if(index == -1) System.out.println(target + " not found in the array");
        else System.out.println(target + " found at index " + index);
    }
}

Enter the input below

Solution approach 2

Since the array is sorted with slight changes, we can also use the binary search algorithm to search for the target element. The algorithm is as follows:

  1. Initialize the start=0 and end=array_length - 1.
  2. Until start <= end, do the following:
    1. Find the mid element using this formula: start + (end - start) / 2.
    2. If the target element is equal to the array element at the index mid, then return the mid index.
    3. If the mid value is greater than zero and the target element is equal to the array element at the index mid-1, then return the mid-1 index.
    4. If the mid value is less than array_length - 1 and the target element is equal to the array element at the index mid+1, then return the mid+1 index.
    5. If the target element is less than the element at index mid, it means the result lies in the left part of the array i.e, from start to mid - 2.
    6. If the target element is greater than the element at index mid, it means the result lies in the right part of the array i.e, from mid + 2 to end.
  3. If the control reaches this step, it means the target element is not found in the array.

The time complexity of the algorithm is O(log(n)), as the search space is reduced by half in every iteration of the loop.

The space complexity of the algorithm is O(1) because no extra space is used.

Modified Binary Search
1 of 6

Code

In the code below, the array is hard coded to [15, 20, 30, 25, 35]. Enter an integer value to be searched in the array.

import java.util.Scanner;
class BinarySearchNearlySortedArray {
    private static int binarySearchNearlySorted(int[] a, int target) {
        int n = a.length;
        int start = 0;
        int end = n-1;
        while(start <= end) {
            int mid = (start + end)/2;
            if(target == a[mid]) {
                return mid;
            }
            if(mid > 0 && target == a[mid-1]) {
                return mid-1;
            }
            if(mid < n-1 && target == a[mid+1]) {
                return mid+1;
            }
            if (target < a[mid]) {
                end = mid-2;
            } else {
                start = mid+2;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[]{15, 20, 30, 25, 35};
        int target = scanner.nextInt();
        int index = binarySearchNearlySorted(arr, target);
        if(index == -1) System.out.println(target + " not found in the array");
        else System.out.println(target + " found at index " + index);
    }
}

Enter the input below

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)