Bidirectional Linear Search Program

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)