Trusted answers to developer questions

Ravi

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]`

.

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 |

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

- Start from the first element of the array.
- Compare every element of the array with the target element.
- If the target element is equal to the array element, then return the index.
- If the target element is not equal to the array element, then move to the next element and repeat this step.

- 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

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

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:

- Initialize the
`start=0`

and`end=array_length - 1`

. - Until
`start <= end`

, do the following:- Find the
`mid`

element using this formula:`start + (end - start) / 2`

. - If the
`target`

element is equal to the array element at the index`mid`

, then return the`mid`

index. - 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. - 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. - 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`

. - 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`

.

- Find the
- 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

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

RELATED TAGS

data structures

algorithms

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses