Searching

Searching

Linear Search

Algorithm:

linearSearch(array, size, element):
    for i -> size
        if array[i] = element
            return i
    return -1

Complexity:

• Time:
  • Worst Case:
  • Average Case:
  • Best Case:
• Space:
  • Worst Case:

Binary Search

Algorithm:

binarySearch(array, size, element):
    start = 0
    end = size - 1
    while (start <= end){
        mid = start + (end - start) / 2;
        if (array[mid] == element){
            return mid
        }
        if (array[mid] < element){
            start = mid + 1
        }
        else {
            end = mid - 1;
        }
    }
    return -1

Complexity:

• Time:
  • Worst Case: )
  • Average Case: )
  • Best Case:
• Space:
  • Worst Case: