When given a sorted list of numbers, binary search is the best algorithm to have in your arsenal. The binary search finds the target element in O(log(n)) time by taking advantage of the sorted property of the list. The algorithm starts with two pointers, the first and the last elements of the list, and compares the middle element against the target. If the middle element matches the target, the algorithm stops and returns true. Assuming the list is sorted in ascending order. If the middle element is less than the target, the left pointer gets moved to one element to the right of the middle pointer, effectively halving the range of the search space. The same efficiency is achieved on the right half of the list when the middle element is greater than the target.

### Example

```
# 0 1 2 3 4 5 6 7 8 idx
# 2 4 6 9 17 18 19 22 23 target = 18
# i m j 0 + (8 - 0)/2 = 4
# 18 19 22 23
# i m j 5 + (8 - 5)/2 = 6
# 18
# imj 5 + (5 - 5)/2 = 5
# done because [m] = target
# return true
```

### Implementation

```
public static boolean binarySearch(int[] arr, int target) {
int n = arr.length, i = 0, j = n - 1;
while (i <= j) {
int m = i + (j - i) / 2;
if (arr[m] == target)
return true;
else if (arr[m] < target)
i = m + 1;
else
j = m - 1;
}
return false;
}
```

### Variants

- Find the first occurrence of the target
- Find the first value greater than the target
- Find the enclosing interval of the target
- Find the index where the element equals the index
- Find the break point of a cyclically sorted array
- Check to see if a given number is a perfect square
- Compute the ℤ square root of a given number
- Compute the ℝ square root of a given number