|
Be the first user to complete this post
|
Add to List |
341. Front and Back Search in an Array
Objective: Given an unsorted array of numbers and a number ‘x’, write a java program to search the number ‘x’ in the array and return its index else return -1.
Example:
Int [] a = {3, 6, 9, 1, 2, 10}
x = 6, Output: 1
x = 2, Output: 4
x = 7, Output: -1
Approach:
Linear Search: Do the linear scan of an array and look for ‘x’ and if find then return its index and return -1.
Time Complexity: O(n)
Front and Back Search:
- Have two pointers, one at the start of the array and one at the end of the array.
- While(start pointer<end pointer)
- Check if any of the pointers is at a number which is equal to ‘x’, means x is found return that pointer’s index
- If x is not found in the step above then increment the start pointer by 1 and decrement the end pointer by 1 and repeat the above step.
- If start pointer > end pointer, return -1.
Time Complexity: O(n/2)
Output:
[3, 6, 9, 1, 2, 10] Element x = 6 is found in array a index: 1 Element x = 2 is found in array a index: 4 Element x = 7 is not found in array