public class LinearSearch {
/**
* @param a Array of unsorted integers
* @param val The value to search for
* @return Array's index if found; -1 if not found.
*/
private static int search(int[] a, int val)
{
for(int k=0; k<a.length; k++){
if(val==a[k])
return k;
}
return -1; // not found
}
}
public class BinarySearch {
/**
* @param a Array of sorted integers
* @param val The value to search for
* @param lo Low index of array
* @param hi High index of array
* @return Array's index if found; -1 if not found.
*/
public static int search(int[] a, int val, int lo, int hi)
{
while(lo<=hi){
int mid = (lo + hi) >>> 1;
int midVal = a[mid];
if(val == midVal){
return mid;
}else if(val < midVal){
hi = mid-1;
}else{
lo = mid+1;
}
}
return -1; // not found
}
/**
* @param a Array of sorted integers
* @param val The value to search for
* @param lo Low index of array
* @param hi High index of array
* @return Array's index if found; -1 if not found.
*/
public static int searchWithRecursive(int[] a, int val, int lo, int hi)
{
int mid = (lo + hi) >>> 1;
int midVal = a[mid];
if(val == midVal)
return mid;
if(val < midVal)
return searchWithRecursive(a, val, lo, mid-1);
else
return searchWithRecursive(a, val, mid+1, hi);
}