/* Include lib */
#include <stdio.h>
#include <assert.h>

/* Define */
#define ARRAY_MAX   16
#define ARRAY_INPUT { 0, 5, 7, 2, 5, 10, -1, 9, \
                      2, 3, 6, 8, 9, 12, -9, 14 }

#define FIND_VALUE  3

int array_input[ARRAY_MAX] = ARRAY_INPUT;

/* API sort array */
int sort_array_from_small(int *arr, int arr_size)
{
  int i, tmp, end = arr_size - 1;

  /* TODO: Check input pointer / size */

  /*
   * Algorithm: there are 2 loop:
   *  - Small loop: Compare each 2 element beside and move large one to right.
   *    Loop until last - 1, so the largest will move to the end.
   *  - Big loop: Loop above without last one to move second largest to right.
   *    Continue until end of array size. 
   */
  while (end > 0) {
    for (i = 0; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
      }
    }

    end--;
  }

  return 0;
}

/* API binary search. Recommend use sorted array. Find and stop */
/* TODO: To find all, should find first one, then continue linear search to find all */
int binary_search(int *arr, int arr_size, int key)
{
  int mid, found = 0, start = 0, end = arr_size - 1;

  printf("\nBinary search value %d\n", key);

  /* TODO: Check input pointer / size */

  while (start <= end) {
    mid = (start + end) / 2;

    if (arr[mid] == key) {
      printf("Find index %d val = %d as expected\n", mid, arr[mid]);
      break;
    } else if (arr[mid] > key) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return 0;
}


/* API linear search */
int linear_search(int *arr, int arr_size, int key)
{
  int i, found = 0;

  printf("\nLinear search value %d\n", key);

  /* TODO: Check input pointer / size */

  for (i = 0; i < arr_size; i++) {
    if (arr[i] == key) {
      printf("Find index %d val = %d as expected\n", i, arr[i]);
      found = 1;
    }
  }

  if (found) {
    return 0;
  } else {
    printf("Nothing find !!\n");
    return -1;
  }
}

/* Main func interract with user */
int main(void)
{
  int i;

  printf("Input array : ");
  for (i = 0; i < ARRAY_MAX; i++)
    printf("%d ", array_input[i]);
  printf("\n");

  /* Linear search */
  linear_search(&array_input[0], ARRAY_MAX, FIND_VALUE);

  /* Sort array */
  sort_array_from_small(&array_input[0], ARRAY_MAX);

  /* Output */
  printf("\nSorted array: ");
  for (i = 0; i < ARRAY_MAX; i++)
    printf("%d ", array_input[i]);
  printf("\n");
  
  /* Binary search */
  binary_search(&array_input[0], ARRAY_MAX, FIND_VALUE);


  return 0;
}