#include<iostream>
using namespace std;
int linearSearch( const int array[], int key, int size )
{
	for ( int i = 0; i < size; i++ ) {
		if ( array[i] == key ) {
		   return i; //return the location in array
	    }
	}
	return -1; //key not found
}

int binarySearch( const int array[], int key, int low, int high )
{
    int middle; //the middle index number of the array
    while ( low <= high ) {
       middle = ( low + high ) / 2;
       if ( key == array[ middle ] ) {
	        return middle;
	   }
	   else if ( key < array[ middle ] ) {
		    high = middle - 1; //reset high index to left side
	   }
	   else {
	        low = middle + 1; //reset low index to right side
	   }
    }
	return -1;   //key not found
}
/*-Steps to do:
Declare variables and array with 5 elements to store integer.
Prompt user to key in 5 integer numbers and store in your array.
Asked you user to key in a search key/ target.
Call you linear search to get the position of the target in the array.
Call you binary search to get the position of the target in the array.
Display the position if you found the value or "Key not found" if the key not in the array*/

int main (){
	int SIZE = 5;
	int num[SIZE];
	int key;
	int check1;
	int check2;

	for (int i = 0;i < SIZE;i++){
		cout << "Please enter number " << i + 1 << " :";
		cin >> num[i];
	}
	cout<<"Please enter the key search number :";
	cin>>key;

		check1=linearSearch(num,key,SIZE);
		if(check1!=-1){
			cout<<"key found " << check1 <<"\n";
		}
		else{
			cout<<"Key not found\n";
		}

		check2=binarySearch(num,key,0,SIZE-1);
		if(check2!=-1){
			cout<<"key found " << check2 <<"\n";
		}
		else{
			cout<<"Key not found\n";
		}

	return 0;

}