Problem statement: What & how do you do binary search ?
METHOD-I:
- A simple approach is to do linear search.
- The time complexity of this approach's algorithm is O(n).
- Another approach to perform the same task is using Binary Search. In case of binary search, array elements must be sorted in ASCENDING order, not in DESCENDING order
- The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).
- Binary search is faster than linear search.
- Algorithm:
- Search a sorted array by repeatedly dividing the search interval in half.
- Begin with an interval covering the whole array.
- If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
- Otherwise narrow it to the upper half.
- Repeatedly check until the value is found or the interval is empty.
METHOD-I:
- public class BinarySearchExe {
- public static void main(String args[]) {
- int arr[] = { 10, 20, 30, 40, 50 };
- binarySearchss(arr, 30);
- }
- public static void binarySearchss(int a[], int key) {
- int start = 0, end = a.length - 1;
- int mid = (start + end) / 2;
- while (start <= end) {
- if (key == a[mid]) {
- System.out.println("key at index: " + mid);
- break;
- } else if (key > a[mid]) {
- start = mid + 1;
- } else {
- end = mid - 1;
- }
- mid = (start + end) / 2;
- }
- if (start > end) {
- System.out.println("key not found!");
- }
- }
- }
Output:
key at index: 2
Time complexity: O(log n)
METHOD-II:
- public class BinarySearchExe {
- public static void main(String[] args) {
- int a[] = { 10, 20, 30, 40, 50 };
- int idx = binarySearch(a, 30);
- System.out.println("key at index: " + idx);
- }
- public static int binarySearch(int a[], int key) {
- int start = 0, end = a.length - 1;
- while (start <= end) {
- int mid = (start + end) / 2;
- if (key == a[mid]) {
- return mid;
- }
- if (key < a[mid]) {
- end = mid - 1;
- } else {
- start = mid + 1;
- }
- }
- return -1;
- }
- }
Output:
key at index: 2
Time complexity: O(log n)
