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,int
key,int
imin,int
imax){
// 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(int
array[], int
key, int
imin, int
imax) {
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