Once you click post assignment, learners in the selected class will immediately be able to see and complete this assignment

Back to Classroom

Binary Search

AP® Computer Science A (Java) Course

Engineers From These Top Companies and Universities Trust EXLskills

1M+ Professionals | 100+ Institutions

This is the EXLskills free and open-source AP® (Advanced Placement®) Java Course. It guides learners via explanation, demonstration, and thorough practice, from no more than a basic understanding of Java, to a moderate level of essential coding proficiency. It is a substantial amount of coursework that represents a typical year of high school-level study or a semester of a University computer science course. This course may also be used to prepare for the AP® Computer Science A exam.

Is this course FREE?

Yes, this a 100% free course that you can contribute to on GitHub here!

As we discussed previously, sequential search can take an excessively long time since they look through every element in an array. This is like flipping through each page of the dictionary from the beginning even if we are trying to find the word "zero". Let's introduce the concept of binary search, which is similar to flipping right to the 'Z' section of the dictionary to start looking for the word "zero". If an array or ArrayList is ordered, the binary search method can be used. Look below and review the functionality of a binary search.

BinarySearchExample.java

package exlcode;
public class BinarySearchExample {
public static void main(String[] args) {
// the array has to be sorted before binary search
int[] exampleVariableOne = {1, 11, 24, 34, 67, 89, 102};
int target = 102;
binarySearch(exampleVariableOne, target);
}
public static void binarySearch(int[] parameterOne, int parameterTwo) {
int index = -1;
int lowEnd = 0;
int highEnd = parameterOne.length - 1;
while (highEnd >= lowEnd) { // Difference of highEnd and lowEnd decreases as the search range narrows
int middle = (lowEnd + highEnd) / 2;
// checks if the middle of the lowEnd and the highEnd is the target
if (parameterOne[middle] == parameterTwo) {
index = middle; // the target is found
break;
} else if (parameterOne[middle] < parameterTwo) {
// changes the lowEnd to narrow the search range
lowEnd = middle + 1;
} else if (parameterOne[middle] > parameterTwo) {
// changes the highEnd to narrow the search range
highEnd = middle - 1;
}
}
if (index == -1) {
System.out.println("Your target integer does not exist in the array");
} else {
System.out.println("Your target integer is in index " + index + " of the array");
}
}
}

Again, a binary search will only work if we have a sorted list. Duplicate values don't affect the search. A binary search starts at the middle of a sorted list and assess if the value it's called to look for is greater than of less than the middle. This initial procedure establishes whether the target value is in the first or second half of the list, at which point the search changes its high and low values to focus on the correct half of the list. Then, the search enters the middle of its chosen half and does the exact same procedure over and over again until the target value is found.

Although you will not need to know how to write your own search methods, you do have to understand what a search method does and how it works in order to use them effectively.