Earlier, we looked at an example to illustrate the working of the Binary Search Algorithm on a sample input array.
Here, we look at another example. Specifically, in this example, the key that we are searching for is actually not present in the array. We see how binary search handles this case.
❀ ✿ ❀
श्रीः
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:
18
✿ ❀ ✿ ❀ ✿
1
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 1
low
1
high
12
mid
6
Key
18
Current search space
A[1 … 12]
✦ Middle element, A[mid] = 37
18 < 37
Key < Middle Element
➜ New search space:
A[1 … 5]
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
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 2
low
1
high
5
mid
3
Key
18
Current search space
A[1 … 5]
✦ Middle element, A[mid] = 17
18 > 17
Key > Middle Element
➜ New search space:
A[4 … 5]
10
[1]
14
[2]
17
[3]
22
[4]
23
[5]
Discarded
New search space
✿ ❀ ✿ ❀ ✿
3
❀ ✿ ❀
श्रीः
Binary Search Algorithm
Pass 3
low
4
high
5
mid
4
Key
18
Current search space
A[4 … 5]
✦ Middle element, A[mid] = 22
18 < 22
Key < Middle Element
➜ No elements left in search space.
All elements discarded.
22
[4]
23
[5]
Discarded
➜ Key not found. Key is not present in the array.
➜ Binary Search Algorithm successfully completed.
✿ ❀ ✿ ❀ ✿
4
(More Algorithms: How to find minimum value in an array? , How to insert element in array? )
Leave a Reply