Search an Element in a Nearly (Almost) Sorted Array - Java Solution

1. Introduction

This blog post discusses an algorithm to search for a target value in a nearly sorted array, where elements are moved to either of their adjacent positions after sorting. This problem is a variation of the standard binary search and requires a slightly different approach.

Problem

Given an array that is sorted but some elements are swapped with their adjacent elements, write an efficient algorithm to search for a target value in this array.

2. Solution Steps

1. Use a modified binary search.

2. At each step, compare the target with the current element, and also check one position before and after.

3. If the target is found at the current, previous, or next position, return the index.

4. If not found, adjust the search range based on the value comparison.

5. If the target is not found in the entire array, return -1.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] arr1 = {10, 3, 40, 20, 50, 80, 70};
        System.out.println("Index of 40: " + modifiedBinarySearch(arr1, 40));

        int[] arr2 = {10, 3, 40, 20, 50, 80, 70};
        System.out.println("Index of 90: " + modifiedBinarySearch(arr2, 90));
    }

    // Method for modified binary search in nearly sorted array
    public static int modifiedBinarySearch(int[] arr, int target) {
        int start = 0, end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            // Check for target at mid, mid-1, and mid+1 positions
            if (arr[mid] == target) {
                return mid;
            }
            if (mid > start && arr[mid - 1] == target) {
                return mid - 1;
            }
            if (mid < end && arr[mid + 1] == target) {
                return mid + 1;
            }

            // Adjust search range
            if (arr[mid] < target) {
                start = mid + 2;
            } else {
                end = mid - 2;
            }
        }
        return -1; // Element not found
    }
}

Output:

Index of 40: 2
Index of 90: -1

Explanation:

The modifiedBinarySearch method efficiently searches for the target in a nearly sorted array. It accounts for the possibility that elements might be swapped with their adjacent elements. 

For the input array [10, 3, 40, 20, 50, 80, 70] and target 40, it finds the index as 2. 

For the target 90, it returns -1, indicating the target is not found.