package algoexpert.easy;

/*

PROBLEM:

Implement Binary Search

Solutions:

1. Recursive - t: O(log n) | s: O(log n)

2. Iterative - t: O(log n) | s: O(1)

*/

public class BinarySearch {

public static void test()

{

int [] testArr = new int[] {0, 1, 21, 33, 45, 45, 61, 71, 72, 73};

int target = 33;

System.out.println(binarySearch(testArr, target));

}

// time : O(log n) | space: O(1)

public static int iterative(int[] array, int target){

int first = 0;

int last = array.length - 1;

while(first <= last)

{

int middle = (first + last) / 2;

if (array[middle] == target) { return middle; }

else if (array[middle] < target) { first = middle + 1;}

else { last = middle - 1;}

}

return -1;

}

// time : O(log n) | space : O(log n) - recursive stack

public static int recursive(int[] array, int target, int first, int last){

if (first > last) {return -1;}

int middle = (first + last) / 2;

if (array[middle] == target) { return middle; }

else if (array[middle] < target) { first = middle + 1;}

else { last = middle - 1; }

return recursive(array, target, first, last);

}

public static int binarySearch(int[] array, int target) {

//return recursive(array, target, 0, array.length - 1);

return iterative(array, target);

}

}