Given an array arr[] of n elements, write a function to search a given element x in arr[].
Examples:
Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 110; Output : 6 Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 175; Output : -1
Bi-directional Linear Search (BLS) can be used to minimize the execution of Linear Search. Linear Search starts from the leftmost element of arr[] and one by one compare x with each element of arr[]. In addition to Linear Search approach, BLS also starts rightmost element of arr[].
Implementation:
C++
#include <iostream> using namespace std; int BidirectionalLinearSearch(int arr[], int count, int searchItem) { for (int i = 0, j = count - 1; i < j; i++, j--) { if (arr[i] == searchItem) { return i; } else if (arr[j] == searchItem) { return j; } } return -1; } int main() { int arr[] = { 4, 6, 3, 5, 8, 9, 0, 2, 1, 7 }; int x = 2; int size = sizeof(arr) / sizeof(arr[0]); int result = BidirectionalLinearSearch(arr, size, x); if (result == -1) cout << "Element is not present in array" << endl; else cout << "Element is present at index " << result << endl; return 0; }
Python
def bidirectional_linear_search(arr, search_item): left, right = 0, len(arr) - 1 while left < right: if arr[left] == search_item: return left elif arr[right] == search_item: return right left += 1 right -= 1 return -1 if __name__ == "__main__": arr = [4, 6, 3, 5, 8, 9, 0, 2, 1, 7] x = 2 result = bidirectional_linear_search(arr, x) if result == -1: print("Element is not present in array") else: print(f"Element is present at index {result}")
Java
public class Main { public static int bidirectionalLinearSearch(int[] arr, int searchItem) { int left = 0; int right = arr.length - 1; while (left < right) { if (arr[left] == searchItem) { return left; } else if (arr[right] == searchItem) { return right; } left++; right--; } return -1; } public static void main(String[] args) { int[] arr = { 4, 6, 3, 5, 8, 9, 0, 2, 1, 7 }; int x = 2; int result = bidirectionalLinearSearch(arr, x); if (result == -1) { System.out.println("Element is not present in array"); } else { System.out.println("Element is present at index " + result); } } }
Output:
Element is present at index 7
Time Complexity: O(log n)