Algorithm of Binary Search | Overview, Definition & Meaning

Binary Search: A Fast Algorithm for Finding Items in Sorted Arrays

Binary search is a fast algorithm used for locating an item in a sorted array. The algorithm works by repeatedly dividing the search interval in half until the item is found or the search interval is empty. In this article, we will explore what binary search is, how it works, and why it is important in computer science.

What is Binary Search?

Binary search is a search algorithm used to find an item in a sorted array. The search interval starts with the entire array. If the value of the search key is less than the middle item of the interval, then the next interval will be the lower half of the current interval. If the value of the search key is greater than the middle item, then the next interval will be the upper half. The search process repeats until the item is found or the search interval is empty.

How Does Binary Search Work?

Binary search works by repeatedly dividing the search interval in half. The algorithm starts by checking the middle item of the search interval. If the search key matches the middle item, then the item has been found. If the search key is less than the middle item, then the search interval is reduced to the lower half of the current interval. If the search key is greater than the middle item, then the search interval is reduced to the upper half of the current interval. The search process repeats until the item is found or the search interval is empty.

Why is Binary Search Important?

Binary search is an important algorithm in computer science because it is more efficient than a linear search for large arrays. A binary search has a time complexity of O(log n), whereas a linear search has a time complexity of O(n). This means that a binary search is much faster than a linear search for large arrays.

Binary Search Algorithm: A Fast Way to Search for Items in Sorted Arrays

Binary search is a search algorithm that works by dividing a sorted array into smaller subarrays and searching for an item in the middle of each subarray. In this article, we will explore the algorithm of binary search and how it works.

Algorithm of Binary Search

The binary search algorithm works by dividing the search interval in half repeatedly until the item is found or the search interval is empty. Here are the steps involved in the algorithm:

1. Set the lower bound to 0 and the upper bound to n-1, where n is the number of items in the sorted array.
2. Calculate the middle index as (lower bound + upper bound) / 2.
3. Compare the search key with the item at the middle index.
4. If the search key matches the item, return the index.
5. If the search key is less than the item at the middle index, set the upper bound to the middle index – 1.
6. If the search key is greater than the item at the middle index, set the lower bound to the middle index + 1.
7. Repeat steps 2-6 until the item is found or the search interval is empty.

Example

Suppose we have a sorted array of integers: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19].

Let’s say we want to search for the number 11 in this array. Here is how the binary search algorithm works:

1. Set the lower bound to 0 and the upper bound to 9 (n-1).
2. Calculate the middle index as (0 + 9) / 2 = 4.
3. Compare the search key (11) with the item at the middle index (9).
4. Since 11 is greater than 9, set the lower bound to 5 (middle index + 1).
5. Calculate the new middle index as (5 + 9) / 2 = 7.
6. Compare the search key (11) with the item at the new middle index (15).
7. Since 11 is less than 15, set the upper bound to 6 (middle index – 1).
8. Calculate the new middle index as (5 + 6) / 2 = 5.
9. Compare the search key (11) with the item at the new middle index (11).
10. Since the search key matches the item, return the index (5).

Therefore, the binary search algorithm returns the index 5 for the number 11 in the sorted array.