A binary search is a searching algorithm whereby half of the array is "eliminated" at each step to find a specific value within a sorted array. For the search to work, the array or collection needs to be sorted numerically or alphabetically. The importance of it being sorted is that we begin searching for a target value in the middle of the array.
Proper definition: Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of a binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). GeeksForGeeks.
public class BinarySearch{
public static void main(String[] args){
int [] numbers = new int[20];
int target = 1;
}
}
Let's say we are looking for the number, 1 (target value), within our array its index will be at [0]. The algorithm will start at the middle value of the array, it will then check to see if the target value is equal to the middle value, but the chances of them being equal on the first step are very slim. The next step of the algorithm will check to see if the target value (1) is greater than or less than the middle value, either of these comparisons will be true so we can then eliminate half of the array. Because the array in the example above is sorted, our target value can't be greater than the middle value, so the algorithm disregards the half it doesn't need. The same process repeats with a smaller array.
Okay now let me show you a real code example.
public class BinarySearch{
public static void main(String[] args){
int [] numbers = new int[20]; // choose any size you want
int target = 1; // target value
for(int i = 0; i < numbers.length; i++){
numbers[i] = i;
}
// there's an easier way to use a binary search but it won't be used
// in this example
}
// binary search method
private static int binarySearch(int[] numbers, int target){
int low = 0; // first index
int high = numbers.length - 1; // last index
while(low <= high){
int middle = low + (high - low) / 2; // middle index
int value = numbers[middle]; // gets the value found
System.out.println("middle" + value);
// checks to if the value is >, < or = to our target
if(value < target) low = middle + 1;
else if(value > target) high = middle - 1;
else return middle; // target found
}
return -1; // target is not found
}
}
To be quite honest, I specifically wrote about this the way I understand it, there is a better explanation somewhere out there, but feel free to copy the code above and mess around with it a bit or even fix it. Let me know in the comments if it runs properly in your chosen IDEs. Or better yet, tell me how you guys understand the binary search algorithm in your own words!