COMP1210: Linear Search Algorithm

Searching Algorithms

Linear Search

• A very basic and simple search algorithm
• Searches an element or value in a given array by traversing the array from the start until the desired element or value is found
• Does not require the array to be sorted
• Steps of implementation:
  • Traverse the array using a for loop
  • In every iteration, compare the target value with the current value of the array
  • If the values match, return the current index of the array
  • If the values do not match, move on to the next array element
  • If no match is found, return -1
• Sample code:

int linearSearch(int values[], int target, int n)
{
      for (int i = 0; i < n; i++)
      {
            if (values[i] == target)
            {
                  return i;
            }
      }
      return -1;
}

Binary Search

• Works only on sorted arrays
• Begins by comparing an element in the middle of the array with the target value
• If the target value matches the element, its position in the array is returned
• If the target value is less than the element, the search continues in the lower half of the array
• If the target value is greater than the element, the search continues in the upper half of the array
• By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration
• Sample code:

int binarySearch(int Arr[], int target, int start, int finish) {
       while (start <= finish) {
             int mid = (start + finish) / 2;
             if (target == Arr[mid])
                   return mid;
             else if (target < Arr[mid])
                   finish = mid - 1;
             else
                   start = mid + 1;
       }
       return -1;
}

Jump Search

• A combination of linear and binary search
• It has been shown that the optimal size of the block is √n
• Steps for Jump Search Algorithms:
  • Set i=0 and m = √n
  • Compare A[i] with item
  • If A[i] != item and A[i] < item, then jump to the next block
  • Repeat step 2 while m < n-1
  • If A[i] > item, then move to the beginning of the current block and perform a linear search
  • Exit