![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Binary Search Algorithm
Introduction
Searching is the process of finding a desired element from a collection of available elements. For example, searching for a particular contact number in a phone directory. Desired phone number is called target and the phone directory is called search space. Search algorithms designed to find whether the target exists in the search space or anything. The search space can be an array or a list or it can be a database.
To understand searching algorithms in clear, let us consider the search space is an array “a” which contains “n” elements and the desired element or target element which we want to search is “k”.
In Binary Search, we compare the target element with the middle element of the given sorted array and based on the outcome, we further divide the array into half and continue until we find the given element. If we find the given target element in the array, the search is successful, else the search process is unsuccessful. Binary Search is an efficient searching algorithm compared to Linear Search and is widely used in many applications. To apply Binary Search the search space should maintain some ordering, incase of linear search there is no need of maintaining the order between the elements.
In real life we use binary search algorithms in many problems without realizing it. For Instance, we have a book which has 1000 pages and if we want to open page number 567, we first try to open some random page and we check the current page number. By looking at the current page number, we try to discard either left side or right side and we continue our search process for remaining pages. If we have to implement the same in computer science, instead of using random search, we always search by picking the middle element of the search space and discard exactly half of the elements of the search space. We continue the same process until we find the target element or there are no elements left in the search space.
Algorithm
1Input : Array a[] of length n and k is the target element2Step 1 : Set index low to 0, high to n-13Step 2 : If low > high return -1 (Search Process is not successful)4Step 3 : Compute mid of the array as mid = (low+high)/25Step 4 : Else a[mid] == k satisfies so return mid (Search Process is successful)6Step 5 : If a[mid] > k , set high = mid-1 and goto step 27Step 6 : Else if a[mid] < k set low = mid+1 and goto step 2
Explanation
Let us understand the binary search algorithm using an example with dry run.
1Input : int[] a = {1, 2, 3, 5, 7, 8, 17, 19, 21, 27, 31} and k = 172Output : 6
1 Iteration1 :2 Step1 : Initialize low = 0 high = 10 (as length of the array is 11)3 Step2 : low <= high (0 <= 10)satisfies so proceed with step34 Step3 : mid = (low+high)/2 = (0+10)/2 = 55 Step4 : check a[mid] is equal to k or not,6 here a[mid] = 8 and k = 17 and 8 ≠ 17, so goto step57 Step5 : check a[mid] > k,8 here a[mid] = 8, k = 17 and 8 > 17 not satisfies, so goto step69 Step6 : check a[mid] < k,10 here a[mid] = 8, k = 17 and 8 < 17 satisfies,11 as low = mid+1 = 6 and repeat step21213 Iteration 2:14 Step2 : low <= high (6<10) satisfies, so goto step315 Step3 : mid = (low+high)/2 = (6+10)/2 = 816 Step4 : check a[mid] is equal to k or not,17 here a[mid] = 21, k=17 and 21 ≠ 17, so goto step518 Step5 : check a[mid] > k,19 here a[mid] = 21, k = 17 and 21 > 17 satisfies,20 as high = mid-1 = 7 and repeat step22122 Iteration 3:23 Step2 : low <= high (6 <= 7) satisfies so proceed with step324 Step3 : mid = (low+high)/2 = (6+7)/2 = 625 Step4 : check whether a[mid] is equal to k or not, here a[mid] = k satisfies,26 Search process gets terminated here and returns mid index which is 6.
Iterative Implementation
- Java
- Python
1public class BinarySearch {23 // Method to search for given value k in an array4 public int search(int[] a, int k) {5 // initialize low to 0 and high to n-16 int low = 0;7 int high = a.length - 1;89 // loop until the search space is exhausted10 // by checking with middle element11 while (low <= high) {12 // compute middle index of the array13 int mid = (low + high) / 2;1415 // compare a[mid] with k (target value),16 if (a[mid] == k) {17 // As target found return mid18 return mid;19 }2021 // if middle element is lesser than target element22 // discard all elements left to middle(including middle element)23 if (a[mid] < k) {24 low = mid + 1;25 }2627 // if middle element is greater than target element28 // discard all elements right to middle(including middle element)29 else {30 high = mid - 1;31 }32 }33 // No match found, so return -1.34 return -1;35 }3637 public static void main(String[] args) {38 // search space39 int[] a = {1, 2, 3, 5, 7, 8, 17, 19, 21, 27, 31};4041 // target element42 int k = 17;4344 int index = new BinarySearch().search(a, k);45 if (index == -1) {46 System.out.println("Target element is not found");47 } else {48 System.out.println("Target element found at index " + index);49 }50 }51}
Recursive Implementation
- Java
- Python
1public class BinarySearchRecursive {23 // Method to search for given value k in an array4 public int search(int[] a, int k){5 // initialize search space using low and high variables6 // initialize low as 0 and high to last index of the array7 int low = 0;8 int high = a.length-1;9 return search(a, k, low, high);10 }1112 // recursive implementation for binary search algorithm13 public int search(int[] a, int k, int low, int high){1415 // when no elements left in the search space16 if(low>high){17 return -1;18 }1920 // computer middle index of the search space21 int mid = (low+high)/2;2223 // compare a[mid] with k (target value)24 if(a[mid] == k){25 // As target found return mid26 return mid;27 }2829 // if middle element is lesser than target element30 // discard all elements left to middle(including middle element)31 if(a[mid] < k){3233 // continue search process for new search space34 return search(a, k, mid+1, high);35 }3637 // if middle element is greater than target element38 // discard all elements right to middle(including middle element)39 // continue search process for new search space40 return search(a, k, low, mid-1);41 }4243 public static void main(String[] args) {44 // search space45 int[] a = {1, 2, 3, 5, 7, 8, 17, 19, 21, 27, 31};4647 // target element48 int k = 17;4950 int index = new BinarySearch().search(a, k);51 if (index == -1) {52 System.out.println("Target element is not found");53 } else {54 System.out.println("Target element found at index " + index);55 }56 }57}
Complexity Analysis
Time Complexity Analysis
In Binary Search, at every iteration we exactly discard half of the elements and continue the search process with the remaining half until we find the target element or there are no elements left in the search space. Each iteration search space becomes exactly half of its size, for example if search space contains n elements
Iteration 1 : (n/2) = n/2^1
Iteration 2 : (n/2)/2 =(n/4) = n/2^2
Iteration 3 : (n/4)/2 =(n/8) = n/2^3
This process terminates when we have one element left in the array and assume the iteration number as k
Iteration k: n/2^k = 1 => k =log2(n)
Time Complexity = log2(n) where n is the number of elements in the search space.
Space Complexity Analysis
Space Complexity of binary search algorithm depends on the way we implement (iterative or recursive)
In iterative implementation, there is no extra auxiliary space used, so space complexity is O(1). In recursive implementation, on average recursive call gets triggered log2(n), that means it uses log2(n) stack space for recursive calls, so space complexity is log2(n).