Searching

Linear Search

Given a array of integers and also key to find in that array. eg

3
10 55
1 2 4 5 7 88 6 45 87 55
5 22
454 785 41 12 65
17 555
1 2 3 4 5 6 7 88 95 45 15 555 14236 141 15 184 12354

int linear_search(int *arr, int n, int target) {
  for (int i=0;i<n;i++) {
    if (arr[i] == target) return i;
  }

  return -1;
}

Binary Search

Given a array of integers in non decreasing order and also key to find in that array. eg

3
10 55
1 2 4 5 7 55 88 99 155 585
5 22
22 85 365 858 993
17 555
1 2 3 4 5 6 7 15 15 45 88 95 141 184 555 12354 14236

int binary_search(int *arr, int n, int target) {
  int left = 0, right = n - 1, mid;

  while (left <= right) {
    mid = left + ((right - left) / 2);

    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}