Binary Search: An Efficient Searching Algorithm

Introduction

Binary search is a widely known and efficient searching algorithm used to find a specific value in a sorted list. It follows a divide-and-conquer approach, reducing the search space by half in each iteration.

Note: Binary Search Only works on sorted List.

How Binary Search Works? Algorithm

1. Initialize Variables:

   • left: The leftmost index of the search space (initially set to 0).

   • right: The rightmost index of the search space (initially set to the last index of the array).

   • target: The value we want to find in the array.

2. Repeat Until left is Less Than or Equal to right:

   • Calculate the middle index mid as start+(end-start)/2.

   • If target is equal to the element at index mid, the search is successful, and we return mid.

   • If the element at index mid is greater than target, set right to mid - 1.

   • If the element at index mid is less than target, set left to mid + 1.

3. Target Not Found:

   • If the loop terminates without finding the target element, the element is not present in the array, and we return a special value (e.g., -1) to indicate the absence.

Pseudocode:

plaintextCopy codeBinarySearch(arr, target):
   left = 0
   right = length of arr - 1

   while left <= right:
      mid = (left + right) / 2

      if arr[mid] == target:
         return mid
      else if arr[mid] > target:
         right = mid - 1
      else:
         left = mid + 1

   // Target element not found
   return -1

Let's illustrate the binary search with an example:

Example: Suppose we have a sorted array arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20], and we want to find the index of the target element target = 12.

1. Initialize left = 0 and right = 9.

2. Calculate mid = (0 + 9) / 2 = 4.

3. Check arr[4] = 10. Since 10 < 12, set left = 4 + 1 = 5.

4. Calculate mid = (5 + 9) / 2 = 7.

5. Check arr[7] = 16. Since 16 > 12, set right = 7 - 1 = 6.

6. Calculate mid = (5 + 6) / 2 = 5.

7. Check arr[5] = 12. The target element is found at index 5, and we return 5.

The binary search algorithm found the target element 12 at index 5, as expected. If the target were not present in the array, the algorithm would have returned -1.

Time Complexity Analysis

Let’s derive the number of divisions mathematically,

If a number n can be divided by 2 for x times:
    2^x = n
Therefore, x = logn (base is 2)

So the overall time complexity is O(logN), where N = size of the given array.

Conclusion

In conclusion, binary search is a highly efficient and reliable searching algorithm but it has significant application beyond its traditional role as a searching technique. Its divide-and-conquer approach and efficient reduction of search space make it a powerful problem-solving tool for various other problems.