Arrays.binarySearch
- Java course
- Beginner
- Lesson 61/116
- 5 min
Learn binary search with Arrays.binarySearch.
Binary search: Arrays.binarySearch
The fast way to search a value in a sorted array is Arrays.binarySearch. The method returns the index of the value; if it cannot find it, it returns a negative number.
int[] nums = {1, 4, 7, 9};
int i = Arrays.binarySearch(nums, 7);
// i = 2Important: if the array is not sorted, the result is undefined. That is why you call Arrays.sort first. Binary search is very fast because it halves the search range at each step.
Return value when not found
When binarySearch cannot find the value, it returns a negative number. It does not just say "not found"; it also tells the position where the value would belong.
int[] nums = {1, 4, 7, 9};
int i = Arrays.binarySearch(nums, 5);
// i = -3 (5 should sit between 4 and 7)The rule is -(insertionPoint) - 1. In practice you check i < 0, conclude the value is missing, and move on.
Practice Look up a student id
Sort the ids below, then search for 103 with Arrays.binarySearch and print the found index.
Starter code
public class Main {
public static void main(String[] args) {
int[] ids = {105, 101, 103, 102};
// First sort the array
// Search for 103 using binary search
// Print the found index
}
}Sample solution
Arrays.sort(ids);
int i = Arrays.binarySearch(ids, 103);
System.out.println(i);Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Order the steps: binary search flow
| Term | Meaning |
|---|---|
1 |
Sort the array |
2 |
Pick the middle element |
3 |
Compare with the target |
4 |
Halve the range |
2 What is the precondition of binarySearch?
- The array must be sorted
- The array must have at least 10 elements Correct answer
- The array must contain only even numbers
- The array must have no duplicate elements
Explanation: On an unsorted array the result is undefined.
3 Fill in the blank: sort and search
int[] nums = {9, 1, 7, 4};
Arrays.sort(nums);
int i = Arrays.____(nums, 7);int[] nums = {9, 1, 7, 4};
Arrays.sort(nums);
int i = Arrays.binarySearch(nums, 7);Explanation: Arrays.binarySearch performs the search.