Binary search requires that the array or collection is already sorted.
Binary search checks the element in the middle of the collection. If the search element is smaller or greater than the found element, then a sub-array is defined which is then searched again. If the searched element is smaller than the found element, then the sub-array is searched from the start of the array until the found element. If the searched element is larger than the found element, then the sub-array is searched from the found element until the end of the array. Once the searched element is found or the collection is empty then the search is over.
It can be done by using divide and conquer method or recursive method
1) Divide and conquer method
public class BinarySearch {
public static boolean binarySearch(int[] input, int element) {
int start = 0;
int end = input.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (element == input[mid]) {
return true;
}
if (element < input[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};
System.out.println(binarySearch(arr, 12));
System.out.println(binarySearch(arr, 200));
}
}
output:
true
false
2) Recursive method
public class RecursiveBinarySearch {
public static boolean binarySearch(int[] input, int start, int end, int element) {
if (start < end) {
int mid = start + (end - start) / 2;
if (element < input[mid]) {
return binarySearch(input, start, mid, element);
} else if (element > input[mid]) {
return binarySearch(input, mid+1, end , element);
} else {
return true;
}
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};
System.out.println(binarySearch(arr, 0, arr.length, 16));
System.out.println(binarySearch(arr, 0, arr.length,200));
}
}
output:
true
false
Performance
Best case :- O(1) if the element found in the middle element (pivot element).
Average and worst case :- O(log n) for each check it divides array into sub array. For example if there is a 100 element in a array. Total element search is 10.
Disadvantage:-
Binary search cannot be applied on the array which is not sorted.
Click to view more:- Algorithms and its performance
No comments:
Post a Comment