---
title: "Binary search with algorithm and example"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:binary-search-algorithm-example"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/binary-search-algorithm-example
site: BCT Engineering
---

# Binary search with algorithm and example

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2073 Magh, 8 marks; 2070 Bhadra, 6 marks; 2073 Bhadra, 3 marks; 2072 Magh, 4 marks (asked 4 times)
- Video: [Lec-15: Binary Search in Data Structure by #Naina Mam](https://www.youtube.com/watch?v=9HlbVEVt_Y0) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/binary-search-algorithm-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Write down the algorithm for binary search with suitable example. Explain a binary search with example.

## Short answer

Binary search on a sorted array: compare key with middle element, discard half, repeat. Worst-case O(log n). Example: searching 41 in [5,12,18,23,30,41,56] finds it at index 5 after two comparisons.

## Answer

Binary search finds a key in a **sorted** array by repeatedly comparing it with the middle element and discarding the half that cannot contain it.

#### Algorithm
```text
BINARYSEARCH(a, n, key)
1. low = 0, high = n - 1
2. while low <= high
3.     mid = (low + high) / 2
4.     if key == a[mid]  return mid        // found
5.     else if key < a[mid]  high = mid - 1  // search left half
6.     else  low = mid + 1                 // search right half
7. return -1                               // not found
```

```c
int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
```

#### Example: search 23 in 5, 12, 18, 23, 30, 41, 56 (index 0 to 6)
| Step | low | high | mid | a[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 23 | equal, found |

Search 41 in the same list:

| Step | low | high | mid | a[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 23 | 41 > 23, low = 4 |
| 2 | 4 | 6 | 5 | 41 | found at index 5 |

If the key is absent (say 20), low becomes greater than high and the search stops with "not found".

**Complexity:** each step halves the range, so the worst case is O(log₂ n) comparisons (best case O(1)). The list must already be sorted and stored in an array that allows direct access.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What must be true for binary search?
   A. Array is sorted with direct access
   B. List is unsorted
   C. Keys are distinct integers only
   D. Data is in a linked list
   Answer: A. Discarding halves requires sorted data. (Key point: Precondition)

2. How is mid computed?
   A. (low + high) / 2
   B. low + 1
   C. high - 1
   D. n / 2 always
   Answer: A. The middle of the current range. (Key point: Mid)

3. If key > a[mid], what next?
   A. high = mid - 1
   B. low = mid + 1
   C. return mid
   D. stop
   Answer: B. Key lies in the right half. (Key point: Update)

4. How does the search detect an absent key?
   A. mid becomes 0
   B. low becomes greater than high
   C. a[mid] is negative
   D. after n steps
   Answer: B. The range becomes empty; return -1. (Key point: Not found)

## Related in Data Structure and Algorithm

- [Binary search for 54 in sorted data](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-54) — Data Structure and Algorithm, chapter 8
- [Binary search for 89; hash functions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-89-hashing) — Data Structure and Algorithm, chapter 8
- [Complexity of binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-complexity) — Data Structure and Algorithm, chapter 8
- [Sequential vs binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asequential-vs-binary-search) — Data Structure and Algorithm, chapter 8
- [BST properties and recursive search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-properties-recursive-search) — Data Structure and Algorithm, chapter 6
- [Binary tree traversals; preorder of BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-tree-traversal-methods-preorder) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [File stream; student binary file program](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Afile-stream-student-binary) — Object Oriented Programming, chapter 8
- [Binary file of 48 students; highest mark](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afile-binary-48-students-highest) — Computer Programming, chapter 10
- [Decoupled load flow assumptions and algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Adecoupled-assumptions-algorithm) — Power System Analysis II, chapter 2, asked 2×
- [Bresenham's algorithm for all slopes](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Abresenham-all-slopes) — Computer Graphics, chapter 2