## Problem Statement

Given an array `a[]`

that is sorted, but after sorting, some elements are moved to either of the adjacent positions, i.e., `a[i] `

may be present at `a[i+1]`

or `a[i-1]`

.

Write an efficient algorithm to search for a `target`

value in this array. Note that, the element `a[i]`

can only be swapped with either `a[i+1]`

or `a[i-1]`

.

For example consider the array `{2, 3, 10, 4, 20}`

, where `4`

is moved to next position and `10`

is moved to previous position.

**Example 1:**

```
Input: arr[] = {10, 3, 40, 20, 50, 80, 70}, target = 40
Output: 2
Output is index of 40 in the given array
```

**Example 2:**

```
Input: arr[] = {10, 3, 40, 20, 50, 80, 70}, target = 90
Output: -1
-1 is returned since the target value is not found
```

## Binary Search to find an element in a nearly (almost) sorted array

Given that the array is sorted but an element can be moved to its adjacent positions, we can apply binary search with some tweaks to search for the `target`

value in `O(log n)`

time complexity:

- First, compare the
`target`

value with all the 3 elements in the middle (since the middle element can be swapped with its adjacent elements). If the`target`

is equal to any of the middle 3 elements, then we return the corresponding index. - Otherwise, if
`target < a[mid]`

, then we can discard the upper half of the array and continue the search in the lower half by setting`end=mid-2`

. This is because all the elements after`mid+2`

(upper half of the array) will be greater than`a[mid]`

so no point searching for`target`

in the upper half. - If
`target > a[mid]`

, then continue the search in the upper half of the array by setting`start=mid+2`

. (All the elements before`mid-2`

will be smaller than`a[mid]`

so we can discard the lower half of the array)

Let’s look at the implementation:

```
import java.util.Scanner;
class SearchInNearlySortedArray {
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 keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.printf("BinarySearchNearlySorted(%d) = %d%n", target, binarySearchNearlySorted(a, target));
}
}
```

```
# Output
$ javac SearchInNearlySortedArray.java
$ java SearchInNearlySortedArray
7
10 3 40 20 50 80 70
40
BinarySearchNearlySorted(40) = 2
$ java SearchInNearlySortedArray
7
10 3 40 20 50 80 70
90
BinarySearchNearlySorted(90) = -1
```