Implement Binary Search Algorithm
Publish Date: 2022-09-25
let’s play a game called guess the number. suppose I have a number chosen in my mind between 1 and 100 and you have to find that exact number, and with every guess, I’ll tell you if your guess is too low, too high, or correct.
One way you might think of is to start by 1.2.3.. until you find the number or reach 100. or in the same way go from inverse 100,98,97... until you find the number or reach 1, the end of the numbers list. But another way is to try a random number by chance, you might succeed the first time, and mostly you may not, but where to start from ?
Here’s a better way, you start with 50 :
I: Too low,
you just eliminated half the numbers! So the numbers 1–50 are also low.
Next guess: 75
I: Too high
you again cut down half the remaining numbers!
Next is 63 (halfway between 50 and 75)
…until you find the target.
With each step of the search, you cut the numbers in half and eliminate 50 elements, then 25 then 13 ... until you’re left with only one number:
100 → 50 → 25 → 13 → 7 → 4 → 2 → 1
Binary Search Algorithm
This is a binary search algorithm. You just learned your first algorithm! Where you guess the middle number and eliminate half the remaining numbers every time.
From the previous example, you cut down the search steps from 100 to only 7 steps. a binary search uses logarithm steps of base 2, which means for a list of 100 elements : log2(100) = 6.6438561897747 ~= 7 and 2^6.6438561897747 = 100 .
So, For a list of 1,024 elements, Log2 (1,024 )= 10, because 2 ^10 = 1,024. Therefore, for a list of 1,024 numbers, you’d have to check 10 numbers at most. And If the list is 4 billion items, it takes at most 32 guesses.
In general, for any list of n, a binary search will take Log2(n) steps and O(log(n)) time to run in the worst case, whereas a simple search will take n steps and O(n) time.
Binary search only works when your list is in sorted order. So let’s see how to implement this algorithm in Python, Java, and Scala.
Implement Binary Search in Python
The binary_search function takes its input as a sorted list (array) of elements and a target element number. If the target is in the array, the function returns its position. You’ll keep track of what part of the array you have to search through.
At first we set the lower and upper bounds of our list (-1 means to start our bound "to the left" of the 0th index):
low = -1
high = len(items)
every time, If there isn't at least 1 index between low and high bounds,we've run out of guesses and the number must not be present:
while low + 1 < high:
for each iteration we eliminate the half-length of items, and set the index ~halfway between the low and high
half_length = (high - low) / 2
guess_index = low + half_length
guess_value = items[int(guess_index)]
if the guess equal to target, then we found what we are looking for :
if guess_value == target:
return True
but, if the guess is too high, then the target is to the left, so move higher bound to the left
if guess_value > target:
high = guess_index
however If the guess is too low, then the target is to the right, so move lower bound to the right, and you update low accordingly:
else:
low = guess_index
otherwise we break the loop and return False.
Here’s the full code, where we use a function that take 2 inputs, a list and a target element number:
def binary_search(target, items):
...: low = -1
...: high = len(items)
...: while low + 1 < high:
...: half_length = (high - low ) /2
...: guess_index = low + half_length
...: guess_value = items[int(guess_index)]
...: if guess_value == target:
...: return True
...: if guess_value > target:
...: high = guess_index
...: else:
...: low = guess_index
...: return False
...:
list1 = [1, 4, 8, 12, 20, 40, 60]
if we try to find element 4, it should return True :
print(binary_search(4, list1))
True
however, if we try to search for element does not exist it should return False:
print(binary_search(9, list1))
False
Implement Binary Search In Java
the implementation in java is at most the same, plus the syntax related to the language specification. so here is the full cod of binary search algorithm in Java
public class BinarySearch {
public static boolean binarySearch(int target, int items[]) {
int low = -1;
int high = items.length;
while (low + 1 < high) {
int half_length = (high - low) / 2;
int guess_index = low + half_length;
int guess_value = items[guess_index];
if (guess_value == target) {
System.out.println("Element " + target + " is found at index: " + guess_index);
return true;
} else if (guess_value > target) {
high = guess_index;
} else {
low = guess_index;
}
}
System.out.println("Element " + target + " is not found!");
return false;
}
public static void main(String args[]){
int items[] = {1, 4, 8, 12, 20, 40, 60};
binarySearch(8, items);
binarySearch(15, items);
}
}
the output will be like that:
Element 8 is found at index: 2
Element 15 is not found!
Process finished with exit code 0
you can check and run it to get familiar with it.
Implement Binary Search In Scala
the next snippet shows the implementation of Binary Search algorithm in scala language, you can run it in your favorite editor or using scala prompt:
object Binary_Search {
def binary_search(target:Int, items:Array[Int]):Boolean = {
var low :Int = -1
var high :Int = items.length
while (low + 1 < high ) {
var half_length = (high - low) / 2
var guess_index = low + half_length
var guess_value = items(guess_index)
if (guess_value == target) return true
else if (guess_value > target) high = guess_index
else low = guess_index
}
return false
}
def main(args: Array[String]): Unit = {
val list1:Array[Int] = Array(1, 4, 8, 12, 20, 40, 60)
println(binary_search(25, list1))
println(binary_search(8, list1))
}
}
the output is as expected, 25 does not exist in the array list, so it returns false, and for 8 it is true:
false
true
Process finished with exit code 0
Conclusion
Binary search is a basic search algorithm that can be used in place of linear search which take constant time.
in this article today we learned what is Binary Search, and how to implement it in Python, Java and Scala.