{"id":22598,"date":"2020-11-10T10:41:24","date_gmt":"2020-11-10T05:11:24","guid":{"rendered":"https:\/\/www.mygreatlearning.com\/blog\/binary-search-algorithm\/"},"modified":"2024-09-03T11:24:36","modified_gmt":"2024-09-03T05:54:36","slug":"binary-search-algorithm","status":"publish","type":"post","link":"https:\/\/www.mygreatlearning.com\/blog\/binary-search-algorithm\/","title":{"rendered":"Binary Search Algorithm | What is Binary Search?"},"content":{"rendered":"\n

What is Binary Search?<\/strong><\/h2>\n\n\n\n

Binary Search Algorithm is one of the widely used searching techniques. It can be used to sort arrays. This searching technique follows the divide and conquer strategy. The search space always reduces to half in every iteration.<\/p>\n\n\n\n

Binary Search Algorithm is a very efficient technique for searching but it needs some order on which partition of the array will occur.<\/p>\n\n\n\n

Advantages of Binary Search Algorithm<\/strong><\/h4>\n\n\n\n
    \n
  1. Since it follows the technique to eliminate half of the array elements, it is more efficient as compared to linear search for large data.<\/li>\n\n\n\n
  2. Better time complexity and thus takes less compilation time. <\/li>\n\n\n\n
  3. An improvement over linear search as it breaks the array down in half rather than sequentially traversing through the array elements.<\/li>\n<\/ol>\n\n\n\n

    Limitations of Binary Search Algorithm<\/strong><\/h4>\n\n\n\n
      \n
    1. Binary Search algorithm could only be implemented over a sorted array. <\/li>\n\n\n\n
    2. Small unsorted arrays would take considerate time in sorting and then searching the desired element. So, binary search is not preferred in such cases.<\/li>\n\n\n\n
    3. It has poor locality of reference compared to linear search algorithm when comes to in-memory searching for short intervals.<\/li>\n<\/ol>\n\n\n\n

      Applications of Binary Search<\/strong><\/h4>\n\n\n\n
        \n
      1. This algorithm is used to search element in a given sorted array with more efficiency.<\/li>\n\n\n\n
      2. It could also be used for few other additional operations like- to find the smallest element in the array or to find the largest element in the array.<\/li>\n<\/ol>\n\n\n\n

        Binary Search Pseudocode<\/strong><\/h2>\n\n\n\n
          \n
        1. We are given an input array that is supposed to be sorted in ascending order.<\/li>\n\n\n\n
        2. We take two variables which will act as a pointer i.e, beg, and end.<\/li>\n\n\n\n
        3. Beg will be assigned with 0 and the end will be assigned to the last index of the array.<\/li>\n\n\n\n
        4. Now we will introduce another variable mid which will mark the middle of the current array. That will be computed as (low+high)\/2.<\/li>\n\n\n\n
        5. If the element present at the mid index is equal to the element to be searched, then just return the mid index.<\/li>\n\n\n\n
        6. If the element to be searched is smaller than the element present at the mid index, move end to mid-1, and all RHS will get discarded.<\/li>\n\n\n\n
        7. If the element to be searched is greater than the element present at the mid index, move beg to mid+1, and all LHS will get discarded.<\/li>\n<\/ol>\n\n\n\n

          Binary Search Algorithm<\/strong><\/h2>\n\n\n\n

          Iterative approach<\/strong><\/h4>\n\n\n\n
          binarySearch(arr, size)\n\t\t   loop until beg is not equal to end\n    midIndex = (beg + end)\/2\n    if (item == arr[midIndex] )\n        return midIndex\n    else if (item > arr[midIndex] ) \n        beg = midIndex + 1\n    else                       \n        end = midIndex - 1<\/code><\/pre>\n\n\n\n
          Recursive approach<\/strong><\/h4>\n\n\n\n
          binarySearch(arr, item, beg, end)\n    if beg<=end\n        midIndex = (beg + end) \/ 2 \n        if item == arr[midIndex]\n            return midIndex\n        else if item < arr[midIndex]        \n            return binarySearch(arr, item, midIndex + 1, end)\n        else                              \n            return binarySearch(arr, item, beg, midIndex - 1)\n    \n    return -1<\/code><\/pre>\n\n\n\n
          Binary Search Algorithm Dry Run<\/strong><\/h4>\n\n\n\n
            \n
          1. Item to be searched=20<\/li>\n<\/ol>\n\n\n\n
            input:<\/p>\n\n\n\n
            0<\/td>1<\/td>2<\/td>3<\/td>4<\/td><\/tr>
            10<\/td>11<\/td>16<\/td>20<\/td>23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
            beg=0, end=4, mid=2\t<\/p>\n\n\n\n
            0<\/td>1<\/td>2<\/strong><\/td>3<\/td>4<\/td><\/tr>
            10<\/td>11<\/td>16<\/strong><\/td>20<\/td>23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
            beg=3, end=4, mid=3\t<\/p>\n\n\n\n
            0<\/td>1<\/td>2<\/td>3<\/strong><\/td>4<\/td><\/tr>
            10<\/td>11<\/td>16<\/td>20<\/strong><\/td>23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
            Element found at index 3, Hence 3 will get returned.<\/p>\n\n\n\n
            2. Given is the pictorial representation of binary search through an array of size 6 arranged in ascending order. We intend to search the element 78:<\/p>\n\n\n
            \"Binary<\/figure>\n\n\n\n
            Binary Search Time Complexity<\/strong><\/h2>\n\n\n\n