Searching

Linear Search

Linear/Sequential Search

C#

int? LinearSearch(int[] array, int target){
    int n = array.Length - 1;
    for(int i = 0; i <= n; i++){
        if(array[i] == target)
            return i;
    }
    return -1;
}

Python

def linear_search(array, target):
    for i in range(0, len(array)):
        if (array[i] == target):
            return i
    return -1

Time Complexity: O(n)

Binary Search

• Binary search works only on a sorted set of elements.

Binary Search

C#

int? BinarySearch(int[] array, int target){
    var startIdx = 0;
    var endIdx = array.Length - 1;
    while(startIdx <= endIdx){
        var middleIdx = (startIdx + endIdx) / 2;
        var middleItem = array[middleIdx];
        if(target < middleItem)
            endIdx = middleIdx - 1;
        else if(target > middleItem)
            startIdx = middleIdx + 1;
        else
            return middleIdx;
    }
    return -1;
}

• Using Recursion:

int? RecursiveBinarySearch(int[] array, int target, int low, int high){
    if(low > high)
        return -1;
    
    var middleIdx = (low + high) / 2;
    var middleItem = array[middleIdx];
    if(target < middleItem)
        return RecursiveBinarySearch(array, target, low, middleIdx - 1);
    else if(target > middleItem)
        return RecursiveBinarySearch(array, target, middleIdx + 1, high);
    else
        return middleIdx;
}

Python

• Using Recursion

def rec_binary_search(array, target, low, high):
    if high >= low:
        mid = low + (high - low) // 2
        if target < array[mid]:
            return rec_binary_search(array, target, low, mid-1) # left half
        elif target > array[mid]:                                   
            return rec_binary_search(array, target, mid + 1, high) # right half
        else:                                                       
            return mid
    else:
        return -1

Time Complexity: O(log n)

Fact

If all the names in the world are written down together in order and you want to search for the position of a specific name, binary search will accomplish this in a maximum of 35 iterations.

Linear Search < Binary Search