Table of Contents
Introduction
Let’s learn today about an efficient Searching Algorithm, i.e., Binary Search. It is also known as half interval search, logarithmic search, and binary chop.
It is a searching algorithm that helps find the element in the array and return the respective index. Additionally, we could also return a flag value to denote the element does not exist.
Binary Search follows the divide and conquer policy, i.e., searches an element by repeatedly dividing the array into two parts for every comparison.
Note: It can only be applied on sorted arrays or the functions which are monotonic in nature.
So, we begin the search by defining two pointers – low and high. Low points to index 0 and high points to arr.length-1 index. Also, let the array be sorted in ascending order. Then we repeatedly find the middle element and compare it with the target element. Now three scenarios are possible:
If middle element = target element => our search ends as the target element is found
If middle element > target element => we move towards left side
If middle element < target element => we move towards right side
So, here let’s say we have to search element 50 in our given array.
We define our low pointer = 0, high pointer = 6 (index).
Then we define a loop where we work till low < high.
Then we find mid = (low+high)/2.
Note: If the constraints (i.e., the array length is of order O(10^9), the above formula could result in overflow error, and hence then, we should use mid = (low + (high-low)/2). This would also give the same answer but prevent an overflow error.
Step 1: First, we find mid = (0+6)/2 = 3 => mid element = 45. Since 45 < 50(our target element) => we move towards the right by changing our low = mid+1.
Step 2: Now, we again find mid = (4+6)/2 = 5 => mid element = 71. Since 71 > 50(our target element) => we move towards left by changing our high = mid-1
Step 3: Now, we find mid = (4+5)/2 = 4 => mid element = 50. Since 50 = 50(our target element) => Our target element is found and hence we return true, or the respective index(i.e., 4 here) depending upon our question and breaks from the loop.
If we cannot find the target element in the given array, we would return -1(or any flag value) or false.
So, this particular searching algorithm is known as Binary Search as in each iteration, the array is further divided into two halves.
Implementation in C++/Java/Python
Let’s have a look at its implementations in various languages –
C++
#include<iostream> using namespace std; int main() { // Enter Input array int n = 0; cout<<"Enter size of array: "; cin >> n; int arr[n]; cout<<"Enter Numbers: "; for(int i = 0; i < n; i++) cin>>arr[i]; // Input the target element cout<<"\nEnter a Number to Search: "; cin>>num; // Apply Binary Search int index = -1; // -1 is the flag value int low = 0; int high = n-1; while (low <= high) { int mid = low + (high - low) / 2; // Check if target element is present at mid if (arr[mid] == num) index = mid; break; // If num greater than arr[mid], ignore left half if (arr[mid] < num) low = mid + 1; // If num is smaller than arr[mid], ignore right half else high = mid - 1; } if (index == -1) cout << “\nElement not found”; else cout<<"\nFound at Index No."<< index; cout << endl; return 0; }
Output:
Enter size of array: 10 Enter Numbers: 3 2 4 5 6 7 8 9 10 11 Enter a Number to Search: 5 Found at Index No. 3
Java
#import java.util.*; public static void main(String[] args){ Scanner s = new Scanner(System.in); // Input size of array System.out.println("Enter size of array: "); int n = s.nextInt(); // Enter Input array System.out.println("Enter Numbers: "); for(int i=0; i<n; i++) arr[i] = s.next(); // Input the target element System.out.println("Enter a Number to Search: "); int num = s.next(); // Apply Binary Search int index = -1; // -1 is the flag value int low = 0; int high = n-1; while (low <= high) { int mid = low + (high - low) / 2; // Check if target element is present at mid if (arr[mid] == num) index = mid; break; // If num is greater than arr[mid], ignore left half if (arr[mid] < num) low = mid + 1; // If num is smaller that arr[mid], ignore right half else high = mid - 1; } if (index == -1) System.out.println(“Element not found”); else System.out.println("Found the target element at Index No."+ index); }
Output:
Enter size of array: 10 Enter Numbers: 3 2 4 5 6 7 8 9 10 11 Enter a Number to Search: 5 Found at Index No. 3
Python
// Perform Binary Search def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - l) // 2; # Check if num is present at mid if arr[mid] == num: return mid # If num is greater than arr[mid], ignore left half elif arr[mid] < num: low = mid + 1 # If num is smaller than arr[mid], ignore right half else: high = mid - 1 # element not present return -1 # Driver Code arr = [ 2, 3, 4, 10, 40 ] num = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, num) if result != -1: print ("Element is present at index % d" % result) else: print ("Element is not present in array")
Output:
Element is present at index 3
Time and Space Complexity
Time Complexity–
Best Time Complexity: O(1) as if the element is present at the middle index, only one comparison is required.
Average Time Complexity: It is the average of time complexities to find the element at every index. So, since the array gets divided into half in every iteration, it follows:
n -> n/2 -> n/4 -> n/8….. n/(2^k)
So, follows an Recurrence Relation : T(n) = T(n/2) + c (where c is constant)
This relation could be solved using a Recurrence Tree or Master Method, hence giving a complexity of O(log n (base 2)).
Worst Time Complexity: O(logn (base 2)) due to the recurrence relation.
Space Complexity: O(1) as we aren’t utilizing or creating any space apart from the given array length as an input.
where n is no of elements in an array
Advantages and Applications of Binary Search
- It’s extremely simple to understand both concepts wise and implementation wise.
- Although it requires a sorted array, it is extremely useful to efficiently search an element in long lists as it breaks down the entire collection into half in every iteration.
- When the target element matches the middle element of the array, the searching work is done in O(1).
Linear Search VS Binary Search
Linear Search | Binary Search |
It uses an iterative or sequential approach. | It uses a divide and conquer approach. |
It does not depend on the arrangement of elements in an array. | It requires a sorted arrangement of elements (either ascending or descending). |
Worst-case time complexity of the linear Search is O(N) | Worst-case time complexity of the binary Search is O(log2N). |
It sequentially access the elements | It accesses the data randomly |
It performs equality comparisons | it performs ordering comparisons |
Best Case is when an element is found at 1st position. | Best Case is when an element is found at the middle position. |
Less Complex | More Complex |
Less efficient | More efficient |
Frequently Asked Questions
In Computer Science, Binary Search is a method for finding a target element in a sorted array by repeatedly dividing the search interval in half.
There are various types of searching algorithms like jump search, binary Search, interpolation search, fibonacci Search etc.
It is called Binary Search as it follows a divide and conquer approach by repeatedly splitting the search space in 2 halfs. Hence, It is also called Dichotomic Search (literally: “that cuts in two”)
Binary Search is faster than Linear Search as The worst-case time complexity of the linear Search is O(N) while Binary Search has O(log2N). But Binary search can only be applied if the array is sorted. However, there is no such condition for Linear Search.
Key Takeaways
In this blog, we learned how to apply Binary Search on the given array.
- It is also known as half interval search, logarithmic Search and binary chop.
- In it, we split the search interval in half in every interval following the divide and conquer approach, reducing the target element’s search space.
- It works for sorted arrays only.
- Its Best Case Time Complexity is O(1), but Worst Case Time Complexity is O(logn), where n is the number of elements in an array.
Check out more blogs on Linear Search to read more about these topics in detail. And if you liked this blog, share it with your friends!
By: Raksha Jain
Leave a Reply