Linear Search

They are 2 search method in an array

  1. Linear search
  2. Binary search

  • Linear search : Size = 10 Length = 10

  • All the elements must be unique here

  • The value you are searching is called key, In linear search we search the key element one by one linearly

  • We search the element by comparing it with the key value

• The result of the search is the location of the element where its present (index number), it is very useful in accessing the element in the list

  • If the element is not found throughout the list that means it is not present in the list therefore search is unsuccessful

Syntax:


int LinearSearch(struct Array arr, int key) {
  int i;
  for(i = 0; i < arr.length; i++) {
    if(key == arr.A[i])
      return i; //if search is successful it ends here
  }

  return -1; // if search unsuccessful returns -1
}
  • When you are searching for a key element there is a possibility that you are searching the same element again
  • To improve the speed of comparison, you can move a key element repeatedly search one step forward. This method is called transposition

void swap(int *x, int *y) {
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

int LinearSearch(struct Array *arr, int key) {
  int i;
  for (i = 0; i < arr->length; i++) {
    if (key == arr->A[i]) {
      swap(&arr->A[i], &arr->A[i - 1]);
      return i;
    }
  }

  return -1;
}
  • The second method is you can directly swap the key element to the first element this process is called move to head. The next search for the same element becomes faster

int LinearSearch(struct Array *arr, int key) {
  int i;
  for (i = 0; i < arr->length; i++) {
    if (key == arr->A[i]) {
      swap(&arr->A[i], &arr->A[0]);
      return i;
    }
  }

  return -1;
}
  • Binary Search : always check for a key element in the middle of a sorted list, and split the list into two.
  • For performing binary search, we need three index variables: lower, higher and mid. This mid is low + high divided by 2, and we will take the floor value.
  • Low should be pointing at index 0, and high should be pointing at the end of the list.

int BinarySearch(struct Array arr, int key) {
  int l, mid, h;
  l = 0;
  h = arr.length - 1;

  while (l <= h) {
    mid = (l + h) / 2;

    if (key == arr.A[mid])
      return mid;
    else if (key < arr.A[mid])
      h = mid - 1;
    else
      l = mid + 1;
  }

  return -1;
}

Binary Search - Recursive Version


int RBinSearch(int a[], int l, int h, int key) {
  int mid;

  if (l <= h) {
    mid = (l + h) / 2;
    if (key == a[mid])
      return mid;
    else if (key < a[mid])
      return RBinSearch(a, l, mid - 1, key);
    else
      return RBinSearch(a, mid + 1, h, key);
  }

  return -1;
}

int main() {
  struct Array arr = {{2, 3, 4, 5, 6}, 10, 5};

  printf("%d\n", RBinSearch(arr.A, 0, arr.length, 5));

  return 0;
}