Binary search or half-interval search is a fast search algorithm to find the position of a target value in a sorted array. The run-time complexity of this algorithm is Ο(log n).

In binary search, the target value is compared to the middle element of the array; if they are not equal, the half of array which target can not lie, is eliminated and the search continues in the remaining half until it is successful.

## 1. Algorithm

- Set L to 0 and R to n − 1.
- If L > R, the search terminates as unsuccessful.
- Set m (the position of the middle element) to the floor of (L + R) / 2.
- If A[m] < T(target value), set L to (m + 1) and go to step 2. If A[m] > T, set R to (m – 1) and go to step 2.
- Now Am = T, the search is done; return m.

## 2. Java code

/** * Array should be sorted asc * The implementation is not recursive * Complexity of the algorithm * Best: O(1) * Worst: O(logn) */ public static int binarySearch(int[] array, int val){ int low = 0; int high = array.length - 1; while(low < high){ int mid = (high + low) / 2; if(array[mid] == val) return mid; else if(array[mid] < val) low = mid +1; else high = mid - 1; } return -1; }

### 2.1. Recursive implementation

/** * Array should be sorted asc * The implementation is recursive * Complexity of the algorithm * Best: O(1) * Worst: O(log n) */ public static int binarySearch(int[] array, int val, int low, int high){ int mid = (high + low) / 2; if(high < low) return -1; if(array[mid] == val) return mid; else if(array[mid] < val) return binarySearch(array, val,mid + 1, high); else return binarySearch(array,val,low ,mid - 1); }

Advertisements