Binary Search Algorithm in Data Structure with Explanation

Binary search is a very efficient searching technique for finding an element in a sorted Array. This method follows the divide and conquers approach to perform a searching operation.

Suppose we have 10,000 sorted elements in an array and we want to search a target value in that array. If we follow linear searching, then in the worst case, we have to compare target value with all 10,000 elements in the list but when we use binary search, we need only log₂n comparison which means 14 comparisons only in the worst case when we have to compare with all 10,000 elements.

So you can see how binary search is efficient for more massive data in comparison to the linear searching method. Binary search is also known as a half-interval search and logarithmic search in computer science.

In this technique, we first find the middle index element from the sorted array, and then we break the array or list into two equal half and then compare the target value with the middle element.

• If the target value is equal to the middle value, then return the middle-value index means search value found in the middle.
• If the target value is greater than the middle value, then the next search will only be done on the second half array which is right of the middle index.
• If the search value is smaller than the middle value, then the next search will be done in the first half of the array which is left of the middle index.
• And if the search value is not found anywhere, it will return -1 or any message like “no item found”.

Why Binary search is needed ?

Binary search is needed when we want to find an element in a sorted array or list much faster than checking each element one by one. Instead of going through every item like in linear search, binary search divides the array or list into halves and eliminates one half at each step. This makes it much quicker, especially for large arrays or lists, because the number of comparisons grows very slowly as the size increases. It is very useful when computational time is important and the data in the array or list is already sorted.

How Binary Search Works

1. Start with calculating Middle: Find the middle index of the sorted list by the formula
   • (start index + last index )/2.
2. Compare: Check if the value at the middle index is the one you’re looking for. If it is, you’re done!
3. Decide Which Half to Keep: If the value you want is greater than the value at the middle index, ignore the first half of the list . If it’s less, ignore the second half.
4. Repeat: Calculate the new middle index of the list you kept and repeat the process until you find the item or until there’s nowhere left to search.

Binary Search Algorithm

Step 1. Start with a sorted array
Step 2. Find the middle index and divide it into two-part.
Step 3. Compare the search value with the value at the middle index. if the match is found, then return the middle index. If not, then follow step 4 and step 5 accordingly.
Step 4. If the search value is greater than the middle indexed value, then select the right part of the array after division and follow step 2
Step 5. If the search value is lesser than the middle indexed value, then select the left part of the array after division and follow step 2
Step 6. When a match is found, then return the index of the element.
Step 7. If no match is found, then return -1.

Pseudocode for Binary Search

function binary_search(K, n, X) is
    L = 0
    R = n − 1
    while L ≤ R do
        m = round((L + R) / 2)
        if K[m] < X then
            L = m + 1
        else if K[m] > X then
            R = m − 1
        else:
            return m
    return -1

Simple Binary Search Program in C

#include <stdio.h>
int main()
{
  int first, last, middle, n, i, value, arr[500];

  printf("Elements you want in array (less than 500): \n");
  scanf("%d", &n);

  printf("Please Enter %d integer value:\n", n);

  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  printf("Please enter search value: \n");
  scanf("%d", &value);

  first = 0;
  last = n - 1;
  middle = (first+last)/2;

  while (first <= last) {
    if (arr[middle] < value){
      first = middle + 1;
    }
    else if (arr[middle] == value) {
      printf("%d found at array index %d.\n", value, middle);
      break;
    }
    else{
      last = middle - 1;  
    }
    middle = (first + last)/2;
  }
  if (first > last){
    printf("%d isn't present in the list.\n", value);
  }
  return 0;
}

Output:

Example 1 (element found):

Elements you want in array (less than 500): 
5
Please Enter 5 integer value:
10
20
30
40
50
Please enter search value: 
30
30 found at array index 2.

Example 2 (element not found):

Elements you want in array (less than 500): 
5
Please Enter 5 integer value:
10
20
30
40
50
Please enter search value: 
25
25 isn't present in the list.

Explanation of Code

The above program starts by including the standard input/output library with #include <stdio.h> and defines the main() function. It declares variables: first and last to represent the start and end of the array, middle for the middle index, n for the number of elements, i as a loop counter, value for the element to search, and arr[500] to store up to 500 integers.

First, the program asks the user to enter the number of elements in the array and stores it in n. Then it asks the user to input n integers, which are stored in the array arr. After that, the program asks for the value to search in the array. Binary search requires a sorted array, so the program assumes the array is already sorted. It initializes first to 0 (the first index), last to n – 1 (the last index), and calculates the middle index as (first + last) / 2.

The program then enters a while loop that continues as long as first <= last. Inside the loop:

• If the middle element arr[middle] is less than the search value, the program moves the first pointer to middle + 1 to search in the right half of the array.
• If the middle element equals the search value, it prints that the value is found along with its index and exits the loop.
• If the middle element is greater than the search value, it moves the last pointer to middle – 1 to search in the left half of the array.

After each iteration, the middle index is recalculated as (first + last) / 2. If the loop ends without finding the value (first > last), the program prints that the element is not present in the list. Finally, the program returns 0 to indicate successful execution.

Key Points of Binary Search

• Sorted List: It only works if the list is sorted because that’s how it knows which half of the list to keep.
• Efficiency: It’s very fast, especially compared to comparing every item one by one. Imagine searching for one page in a book of 1000 pages. Binary search finds it in just 10 steps or less.
• Implementation: It can be done iteratively, using loops, or recursively, where the function calls itself with a smaller portion of the list each time.

Examples of Binary Search

• Finding a Word in a Dictionary: Just like searching for a word in a dictionary by starting in the middle, then deciding which half of the dictionary to continue searching.
• Looking Up a Contact in a Phone: When you search for a contact in your phone, your phone uses binary search to find the name quickly if your contacts are sorted alphabetically.

Advantages of Binary Search

• Speed: It finds items quickly, even in very large lists, by cutting the search area in equal half each time.
• Simplicity: The concept is straightforward, making it easy to understand and implement.
• Efficiency: Uses fewer steps to find an item, saving time and resources.

Real-Life Application of Binary Search

• In Computer Science: Used in searching algorithms, databases, and handling large datasets where quick search operations are crucial.
• In Everyday Life: Whenever we search by splitting the options in half each time – like checking a player’s rank in a sorted leaderboard.

Conclusion

Binary Search is like a treasure hunt where you cleverly eliminate half of the places where the treasure isn’t hidden each time, dramatically speeding up the discovery process. It improves efficiency and simplicity, proving that a methodical approach often leads to the quickest solutions. Whether through games, searching for contacts, or even deciding between choices, the principles of Binary Search find their way into our daily decision-making, showcasing the power and elegance of this algorithm.