Earlier, we had discussed about the working of the Binary Search Algorithm.
In this post, we’ll look at how it works to search for a specific value in an example array.
(Pls note that low represents the beginning index of the current search space, high represents the ending index of the current search space, and mid is taken as the floor of (low+high)/2. )
✿ ❀ ✿
श्रीः
Binary Search Algorithm
Array A:
10
[1]
14
[2]
17
[3]
22
[4]
23
[5]
37
[6]
42
[7]
46
[8]
51
[9]
65
[10]
68
[11]
71
[12]
Key to search for:
46
✿ ❀ ✿ ❀ ✿
1
sri ramanuja seva
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 1
low
1
high
12
mid
6
Key
46
Current search space
A[1 … 12]
✦ Middle element, A[mid] = 37
46 > 37
Key > Middle Element
➜ Discard the left half of the current search space.
➜ New search space:
A[7 … 12]
10
[1]
14
[2]
17
[3]
22
[4]
23
[5]
37
[6]
42
[7]
46
[8]
51
[9]
65
[10]
68
[11]
71
[12]
Discarded
New search space
✿ ❀ ✿ ❀ ✿
2
sri ramanuja seva
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 2
low
7
high
12
mid
9
Key
46
Current search space
A[7 … 12]
✦ Middle element, A[mid] = 51
46 < 51
Key < Middle Element
➜ Discard the right half of the current search space.
➜ New search space:
A[7 … 8]
42
[7]
46
[8]
51
[9]
65
[10]
68
[11]
71
[12]
Discarded
New search space
✿ ❀ ✿ ❀ ✿
3
sri ramanuja seva
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 3
low
7
high
8
mid
7
Key
46
Current search space
A[7 … 8]
✦ Middle element, A[mid] = 42
46 > 42
Key > Middle Element
➜ Discard the left half of the current search space.
➜ New search space:
A[8 … 8]
42
[7]
46
[8]
Discarded
New search space
✿ ❀ ✿ ❀ ✿
4
sri ramanuja seva
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 4
low
8
high
8
mid
8
Key
46
Current search space
A[8 … 8]
✦ Middle element, A[mid] = 46
46 = 46
Key = Middle Element
➜ Key found at index 8
➜ Binary Search Algorithm has successfully completed.
10
[1]
14
[2]
17
[3]
22
[4]
23
[5]
37
[6]
42
[7]
46
[8]
51
[9]
65
[10]
68
[11]
71
[12]
Array element
Key found
✿ ❀ ✿ ❀ ✿
5
sri ramanuja seva
(You can look at another example here.)
Leave a Reply