A binary search or half-interval search algorithm finds the position of a target value within a sorted array.
Step#1 Find the mid_element of array and compare it to target_value.
Step#2 If target_value == mid_element,
return position
If target_value < mid_element,
then the search continues on the lower half of the array;
If target_value > mid_element,
then the search continues on the upper half of the array.
Step#3 Repeat the Step#2 (eliminating half of the elements) until the target value is either found, or until the entire array has been searched.
Complexity
Worst case performance O(log n)
Best case performance O(1)
Average case performance O(log n)
Worst case space complexity O(1)
Recursive approach
class Recursive {
static int binary_search(int[] array,intkey,intimin,intimax){
// test if array is empty
if (imax < imin) {
// set is empty, so return value showing not found
return -1;
} else {
// calculate midpoint to cut set in half
int imid = (imin+imax)/2;
if (array[imid] > key) {
// key is in lower subset
return binary_search(array, key, imin, imid - 1);
} else if(array[imid] < key) {
// key is in upper subset
return binary_search(array, key, imid + 1, imax);
} else {
// key has been found
return imid;
}
}
}
}
public class BinarySearch {
public static void main(String[] args) {
int[] array={1,4,5,7,8,9};
int key=7;
int idx=Recursive.binary_search(array,key,0,array.length-1);
System.out.println("Using recursive approach.\n Index# "+idx);
}
}
Output:
Using recursive approach.
Index# 3
Iterative approach
class Iterative {
int binary_search(intarray[], intkey, intimin, intimax) {
while (imin <= imax) {
int imid = (imin+imax)/2;
if (array[imid] == key) {
// key found at index imid
return imid;
} else if(array[imid] < key) {
// change min index to search upper subarray
imin = imid + 1;
} else {
// change max index to search lower subarray
imax = imid - 1;
}
}
// key was not found
return -1;
}
}
public class BinarySearch {
public static void main(String[] args) {
int[] array={1,4,5,7,8,9};
int key=7;
idx=Recursive.binary_search(array,key,0,array.length-1);
System.out.println("Using iterative approach.\n Index# "+idx);
}
}
Output:
Using iterative approach.
Index# 3
References:
No comments:
Post a Comment