Imaginary situation: “Assume there was a crime incident at some large building. There is a team of police officers who arrived at the crime scene. They are searching and collecting evidence from different parts of the building.” The question, in our context, is not what the crime is! The relation is how will they search? Does the complete team go in one direction or they get separated? Obviously they divide among themselves. Now, let’s see what is the relation of this situation with our topic.
There is an array of elements and we have to search for the presence of a particular element (say s). We have already discussed one of the search methods; Linear Search. We will take a different approach here in the binary search. Assuming elements in the array are arranged in ascending or descending order, s is searched in the array comparing itself with the middle element (mid) of the array.
If s is greater than the mid, then the search can be performed only in the after or righter part of the mid. Similarly, if s is less than the mid the search can be done only in before or left part of the mid. Since the elements are arranged in an order, we divide the array into halves and search for it. This is similar to the way police teams divide among themselves to search for evidence or criminal. Apologies if example did not show similarity 😁. It will be more clear once we go further.
Let’s say we have an array A with elements= {1,2,3,4,5,6}. The element we have to search for is 5. Here the mid element is 3. Since 5>3, the search is performed in the right part of mid i.e., {4,5,6}. This procedure goes repeatedly until the element is found or the search space is consumed.
Algorithm:
1. Start
2. There is a linear array of size n
3. Input the elements in ascending or descending order.
4. Variables "l" and "u" keeps track of the index of the first and last element of the array or sub array in which the element
is being searched at that instant.
5. Variable mid keeps track of the index of the middle element of that array or sub array in which the element is being searched
at that instant.
6. Stop
Pseudo code:
Procedure for binary search
A ← sorted array
n ← size of array
key ← value to be searched
mid ← midpoint of the array
Set lowerBound = l
Set upperBound = u
function binary
if u>=l
if upperBound < lowerBound then exit
set mid = ( upperBound + lowerBound ) / 2
if A[mid] < key then
lowerBound = mid + 1
recursive function call
if A[mid] > key then
upperBound = mid - 1
recursive function call
if A[midPoint] = key then
key found at location mid
exit
end if
else
element not found
end of funtion binary
end procedure
Code in Java:
import java.util.*;
class BinarySearch{
static Scanner s=new Scanner(System.in);
public static void main(String [] args){
try{
System.out.println("Enter the size of the array: ");
int n=s.nextInt();
int [] arr=new int[n];
int key=0;
System.out.println("Note: Enter the elements in ascending or descending order!!");
System.out.println("Enter the elements of array: ");
for(int i=0;i<n;i++)
arr[i]=s.nextInt();
System.out.println("Enter the element to search for:");
key=s.nextInt();
binary(arr,0,n-1,key);
}
finally{
s.close();
}
}
static void binary(int [] a,int l, int u, int key){
int mid=0;
if(u<l) //When upper boundary of the array is less than the lower boundary, element doesn't exist.
return;
if(u>=l){
mid=(l+u)/2; //Average of lower boundary and upper boundary
if(a[mid]==key) //When the element to be searched is the mid element
System.out.println("Element is found at the index: " + mid+1);
if(key<a[mid]) //If element is less than mid it would lie on the left part of the mid.
binary(a,l,mid-1,key);
if(key>a[mid]) //If the element is greater than the mid, it would lie on the right part of the mid.
binary(a,mid+1,u,key);
}
else
System.out.println("Element is not found");
}
}
Time complexity:
What happens here in the binary search is: the array of size n is broken down in halves at each recursion.
So, n becomes (n/2); (n/2) becomes (n/4) and so on..
n (step 0) → n/2 (step 1) → n/4 (step 2)→…..1 (step where the search space is consumed)
Let’s assume that our search space is consumed at Kth step then
1= n/(2K) K= log2n.
Worst case complexity is O(log2 n).
Average complexity also comes to be O(log n).
If the element is found without traversing i.e. at the zeroth iteration, then time complexity is best case: O(1)
Stay updated for more algorithms and information on other domains.
Techprodezza 
4 thoughts on “Binary Search”