 Tagged
• Algorithm
• Searching
• Binary Search
•

# 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 element 2Step 1 : Set index low to 0, high to n-1 3Step 2 : If low > high return -1 (Search Process is not successful) 4Step 3 : Compute mid of the array as mid = (low+high)/2  5Step 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 2 7Step 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 step3 4   Step3 : mid = (low+high)/2 = (0+10)/2 = 5 5   Step4 : check a[mid] is equal to k or not, 6           here a[mid] = 8 and k = 17 and 8 ≠ 17, so goto step5 7   Step5 : check a[mid] > k, 8           here a[mid] = 8, k = 17 and 8 > 17 not satisfies, so goto step6 9   Step6 : check a[mid] < k, 10           here a[mid] = 8, k = 17 and 8 < 17 satisfies, 11           as low = mid+1 = 6 and repeat step2 12 13 Iteration 2: 14   Step2 : low <= high (6<10) satisfies, so goto step3 15   Step3 : mid = (low+high)/2 = (6+10)/2 = 8  16   Step4 : check a[mid] is equal to k or not, 17           here a[mid] = 21, k=17 and 21 ≠ 17, so goto step5 18   Step5 : check a[mid] > k, 19           here a[mid] = 21, k = 17 and 21 > 17 satisfies,  20           as high = mid-1 = 7 and repeat step2 21
22 Iteration 3: 23   Step2 : low <= high (6 <= 7) satisfies so proceed with step3 24   Step3 : mid = (low+high)/2 = (6+7)/2 = 6 25   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

1. Java
2. Python

```1public class BinarySearch {2
3    // 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;8
9        // loop until the search space is exhausted 10        // by checking with middle element11        while (low <= high) {12            // compute middle index of the array13            int mid = (low + high) / 2;14
15            // compare a[mid] with k (target value),16            if (a[mid] == k) {17                // As target found return mid18                return mid;19            }20
21            // 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            }26
27            // 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    }36
37    public static void main(String[] args) {38        // search space39        int[] a = {1, 2, 3, 5, 7, 8, 17, 19, 21, 27, 31};40
41        // target element42        int k = 17;43
44        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

1. Java
2. Python

```1public class BinarySearchRecursive {2
3    // 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    }11
12    // recursive implementation for binary search algorithm13    public int search(int[] a, int k, int low, int high){14
15        // when no elements left in the search space16        if(low>high){17            return -1;18        }19
20        // computer middle index of the search space21        int mid = (low+high)/2;22
23        // compare a[mid] with k (target value)24        if(a[mid] == k){25            // As target found return mid26            return mid;27        }28
29        // if middle element is lesser than target element30        // discard all elements left to middle(including middle element)31        if(a[mid] < k){32
33            // continue search process for new search space34            return search(a, k, mid+1, high);35        }36
37        // 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    }42
43    public static void main(String[] args) {44        // search space45        int[] a = {1, 2, 3, 5, 7, 8, 17, 19, 21, 27, 31};46
47        // target element48        int k = 17;49
50        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).

• Algorithm
• Searching
• Binary Search
•
...