# binary search java implementation and time complexity

### Summary

In a sorted array seq, use bisection to find v. if the range of this array is [low...high], the V we want is in this range. The way to find is to take the value from low to the middle of high. Let's suppose it is m, to compare with V. if M > V, it means that the V we want to find is in the first half of the array seq, otherwise it is in the second half. No matter in the first half or the second half, cut that part into half again and search again. Repeat the process to find where the V value is.
The implementation of binary search can use loop or recursion.

### java implementation

#### loop

```public static int iterativeSearch(int v, int[] seq) {
int low = 0, high = seq.length - 1;
while (low < high) {
int mid = (low + high) / 2;
int m = seq[mid];
if (v == m) {
return mid;
} else if (v > m) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}}```

#### recursion

```public static int recursionSearch(int v, int low, int high, int[] seq) {
if (low > high) return -1;
int mid = (low + high) / 2;
int m = seq[mid];
if (v == m) {
return mid;
} else if (v > m) {
return recursionSearch(v, mid + 1, high, seq);
} else {
return recursionSearch(v, low, mid - 1, seq);
}
}
｝```

#### Java 8 native implementation

```private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];

if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}