Binary Search
Binary Search is a fast and efficient searching algorithm used to find an element in a sorted array. Instead of checking every element one by one, it repeatedly divides the search space into two equal halves until the required element is found or the search interval becomes empty.
Binary Search follows the Divide and Conquer technique, where the problem is divided into smaller parts during each comparison. Since the search area is reduced by half after every step, Binary Search performs much faster than Linear Search when dealing with large amounts of sorted data.
Necessary Conditions for Binary Search
Before applying Binary Search, the following conditions must be satisfied.
| Condition | Description |
|---|---|
| Sorted Data | The elements must be arranged in ascending or descending order. |
| Random Access | The data structure should allow direct access to the middle element, such as an array. |
| Known Search Key | The element to be searched should be known before starting the search. |
Working Principle
Binary Search compares the search key with the middle element of the array.
- If both are equal, the search is successful.
- If the search key is smaller than the middle element, the left half of the array is searched.
- If the search key is greater than the middle element, the right half of the array is searched.
- This process continues until the element is found or no elements remain.
Step-by-Step Algorithm
Step 1 : Read the sorted array.
Step 2 : Set Low = 0 and High = n - 1.
Step 3 : Calculate Mid = (Low + High) / 2.
Step 4 : Compare the search key with Array[Mid].
Step 5 : If both are equal, return the position.
Step 6 : If Key < Array[Mid], search the left half.
Step 7 : If Key > Array[Mid], search the right half.
Step 8 : Repeat until Low > High.
Step 9 : If the element is not found, display "Element Not Found".
Illustration
Example
Consider the following sorted array.
Array
10 20 30 40 50 60 70 80
Search Key = 70
| Iteration | Low | High | Mid | Middle Element | Action |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 40 | Search Right Half |
| 2 | 4 | 7 | 5 | 60 | Search Right Half |
| 3 | 6 | 7 | 6 | 70 | Element Found |
Complexity Analysis
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(1) | The search key is found at the middle position during the first comparison. |
| Average Case | O(log n) | The search space is reduced by half during every iteration until the element is found. |
| Worst Case | O(log n) | The search continues until only one element remains or the element is not present. |
| Space Complexity | O(1) | The iterative Binary Search algorithm requires only a few variables (Low, High and Mid). |
Advantages
- Much faster than Linear Search for large datasets.
- Reduces the search space by half during every iteration.
- Efficient for searching sorted data.
- Simple and easy to implement.
- Widely used in searching applications and database systems.
Limitations
- Works only on sorted data.
- Sorting the data before searching may require additional time.
- Not suitable for linked lists because direct access to the middle element is not available.
Applications of Binary Search
| Application | Description |
|---|---|
| Dictionary Search | Finding words in a dictionary. |
| Library Management | Searching books arranged in sorted order. |
| Database Systems | Searching indexed records efficiently. |
| Search Engines | Fast searching in sorted datasets. |
| Programming | Used in many searching and optimization problems. |
Leave Comment