package com.chrisstubbs;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        //initialize the array
        int[] arr = {10, 6, 90, 77, 65, 7, 9, 94};
        //linear search will return true since 9 is present in the array
        search(arr, 9);

        //initialize another array
        int[] arr2 = {20, 4, 22, 109, 87, 99, 100, 2};
        //sort the array
        Arrays.sort(arr2);
        //binary search will return false since 101 is not present
        binarySearch(arr2, 101);


    }

    //this search loops through the entire array to search for the key
    public static boolean search(int[] array, int key) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == key) {
                return true;
            }
        }

        return false;
    }

    //this search uses a binary search to search for the key
    public static boolean binarySearch(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;

        while (l <= r) {
            int m = l + (r - l) / 2;
            // Check if x is present at mid
            if (arr[m] == key) {
                return true;
            }
            // If x greater, ignore left half
            if (arr[m] < key) {
                l = m + 1;
            }
                // If x is smaller, ignore right half
            else {
                r = m - 1;
            }
        }
        // if we reach here, then element was not present
        return false;
    }
}