Scribd
Upload
97 views19 pages

Binary Search Algorithm

The document explains the binary search algorithm. It uses divide and conquer to search a sorted array by repeatedly dividing the search space in half and selecting the half in which the target may exist. The algorithm compares the target value to the middle element of the array and then searches either the upper or lower half accordingly, based on whether the target is greater than or less than the middle element.

Uploaded by

Ali Saivi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
97 views19 pages

Binary Search Algorithm

The document explains the binary search algorithm. It uses divide and conquer to search a sorted array by repeatedly dividing the search space in half and selecting the half in which the target may exist. The algorithm compares the target value to the middle element of the array and then searches either the upper or lower half accordingly, based on whether the target is greater than or less than the middle element.

Uploaded by

Ali Saivi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

BINARY SEARCH ALGORITHM

PRO ALI SAIVI


PH # +92 317 00 11 200
ALISAIVI786@GMAIL.COM
BINARY SEARCH ALGORITHM

• BINARY SEARCH ALGORITHM FOLLOW DIVIDE AND CONQUER APPROACH.


• TO PERFORM BINARY SEARCH ARRAY LIST MUST BE IN SORTED ORDER(PREREQUISITE FOR BS).
• PERFORMING A BINARY SEARCH WE NEED TO INDEX POINTERS ONE IS LOW (STARTING INDEX)
AND SECOND IS HIGH (ENDING INDEX).

• A KEY VALUE FOR SEARCH


• A MID POINT VALUE FOR COMPARING KEY VALUE. FORMULA MIDPOINT = (LOW + HIGH)/2
• IF KEY VALUE GREATER THAN MID VALUE THAN HIGH REMAIN SAME & LOW = OLD_MID + 1
• IF KEY VALUE LESS THAN MID VALUE THAN LOW REMAIN SAME & HIGHT = OLD_MID - 1

SaiviCodes © 2020 6/26/2020 2


Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low Mid High

We Find Key = 42 in above Sorted Array List

Low = 1 We Noticed that the key


High = 15 element is greater than Key = 42
its Midpoint we have to Midpoint = 29
Midpoint = [Low + High]/2 leave the first half and
moved to the second 42 >= 29
Midpoint = [1 + 15]/2 Half.
Midpoint = [16]/2
Midpoint = 8

Do Repeat this process Again & Again until value reach’s. we divide and divide array list
until value reach’s. 3
SaiviCodes © 2020 6/26/2020
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Mid Low High

We Find Key = 42 in above Sorted Array List and Value of Midpoints less Than Key so Change
the Low Value
Old_Mid = 8
Low = Old_Mid+1 = [8 + 1] = 9 We Noticed that the key
High = 15 element is Less than its Key = 42
Midpoint we have to Midpoint = 47
Midpoint = [Low + High]/2 leave the Second half
and moved to the first 42 <= 47

Midpoint = [9 + 15]/2 Half.


Midpoint = [24]/2
Midpoint = 12
Do Repeat this process Again & Again until value reach’s. we divide and divide array list
SaiviCodes © 2020 until value reach’s. 6/26/2020 4
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low mid high

We Find Key = 42 in above Sorted Array List and Value of Midpoints Greater Than Key so
Change the High Value
Old_Mid = 12
We Noticed that the key
Low = 9
element is greater than Key = 42
High = Old_Mid – 1 = [12-1] = 11 Midpoint = 36
its Midpoint we have to
leave the first half and
Midpoint = [Low + High]/2 42 >= 36
moved to the second
Half.
Midpoint = [9 + 11]/2
Midpoint = [20]/2
Midpoint = 10
Do Repeat this process Again & Again until value reach’s. we divide and divide array list
SaiviCodes © 2020 until value reach’s. 6/26/2020 5
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

mid Low
high
mid
We Find Key = 42 in above Sorted Array List and Value of Midpoints less Than Key so Change
the Low Value
Old_Mid = 10
Low = Old_Mid + 1 = 10 + 1 = 11 Key = 42
High = 11 We Noticed that the key Midpoint = 36
element is Equal than its
Midpoint = [Low + High]/2 Midpoint. Now the 42 == 42
Search is Complete…
Midpoint = [11 + 11]/2
Midpoint = [22]/2
Midpoint = 11
Value Matched we required 42 Value in Array in this Steps Both the Value are Equal and
SaiviCodes © 2020
Binary Search Algorithm Stop… 6/26/2020 6
SUMMARY

Mid = [Low + High]


No of Steps Low High
/2
1 1 15 [1 + 15]/2 = 8
2 9 15 [9 + 15]/2 = 12
3 9 11 [9 + 11]/2 = 10
4 11 11 [11 + 11]/2 = 11

If we search this value using Linear Search we noticed into array the value = 42 founded at
index = 11 , so we have to search out this key using 11 Comparisons its too hard and take a
lot of Time.
SaiviCodes © 2020 6/26/2020 7
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low Mid High

We Find Key = 30 in above Sorted Array List

Low = 1 We Noticed that the key


High = 15 element is greater than Key = 30
its Midpoint we have to Midpoint = 29
Midpoint = [Low + High]/2 leave the first half and
moved to the second 30 >= 29
Midpoint = [1 + 15]/2 Half.
Midpoint = [16]/2
Midpoint = 8

Do Repeat this process Again & Again until value reach’s. we divide and divide array list
SaiviCodes © 2020
until value reach’s. 6/26/2020 8
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Mid Low High

We Find Key = 30 in above Sorted Array List and Value of Midpoints less Than Key so Change
the Low Value
Old_Mid = 8
Low = Old_Mid+1 = [8 + 1] = 9 We Noticed that the key
High = 15 element is Less than its Key = 30
Midpoint we have to Midpoint = 47
Midpoint = [Low + High]/2 leave the Second half
and moved to the first 30 <= 47

Midpoint = [9 + 15]/2 Half.


Midpoint = [24]/2
Midpoint = 12
Do Repeat this process Again & Again until value reach’s. we divide and divide array list
SaiviCodes © 2020
until value reach’s. 6/26/2020 9
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low high Mid

We Find Key = 30 in above Sorted Array List and Value of Midpoints greater Than Key so
Change the High Value
Old_Mid = 12
We Noticed that the key
Low = 9
element is greater than Key = 30
High = Old_Mid – 1 = [12-1] = 11 Midpoint = 36
its Midpoint we have to
leave the first half and
Midpoint = [Low + High]/2 30 <= 36
moved to the second
Half.
Midpoint = [9 + 11]/2
Midpoint = [20]/2
Midpoint = 10
Do Repeat this process Again & Again until value reach’s. we divide and divide array list
SaiviCodes © 2020 until value reach’s. 6/26/2020 10
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Low
high
mid

We Find Key = 42 in above Sorted Array List and Value of Midpoints greater Than Key so
Change the High Value
Old_Mid = 10
Low = 9 Key = 42
High = Old_Mid – 1 = [10-1] = 9 We Noticed that the key Midpoint = 36
element is Equal than its
Midpoint = [Low + High]/2 Midpoint. Now the 30 <= 31
Search is Complete…
Midpoint = [9 + 9]/2
Midpoint = [18]/2
Midpoint = 9
Do Repeat this process Again & Again until value reach’s. we divide and divide array list
until value reach’s. 6/26/2020 11
SaiviCodes © 2020
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Low
high
mid
We Find Key = 42 in above Sorted Array List and Value of Midpoints greater Than Key so
Change the High Value

We Noticed that the High


Old_Mid = 9
Value is Less than Low
Low = 9
Value now comes to the
High = Old_Mid – 1 = [9-1] = 8
point that High value
never ever be smallest
Low > High (Wrong Case)
value over the Low
Value

Algorithm Stop due to Value not Found in Array


SaiviCodes © 2020 6/26/2020 12
SUMMARY

Mid = [Low + High]


No of Steps Low High
/2
1 1 15 [1 + 15]/2 = 8
2 9 15 [9 + 15]/2 = 12
3 9 11 [9 + 11]/2 = 10
4 9 9 [9 + 9]/2 = 9
5 9 8 Stop Error Occurs

SaiviCodes © 2020 6/26/2020 13


ALGORITHM

SaiviCodes © 2020 6/26/2020 14


Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Log n 8

4 12

2 6 10 14

1 3 5 7 9 11 13 15

15+1 = 16 => log16 base 2 = 4


SaiviCodes © 2020 4 Comparison are Required 6/26/2020 15
Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Log n 8 Min Time – 1 O(1)


Max Time – log n O(log n)
Best Case: O(1)
4 12 Worst Case: O(log n)

2 6 10 14

1 3 5 7 9 11 13 15

If we search Value 65 or 57 so either these values are 56 65


not in array list so it will take 4 comparison as Well 6/26/2020
16
SUMMARY

• BEST CASE IT IS IF YOU ARE SEARCHING FOR A KEY ELEMENT IN THE MIDDLE OF
ARRAY LIST THAT IS BEST CASE AND TIME IS 1 O(1).

• WORST CASE IF YOU ARE SEARCHING FOR A KEY ELEMENT PRESENT ON THE
LEAFE AND AT THE TIME IS LOG N IN WORST CASE O(LOG N).

SaiviCodes © 2020 6/26/2020 17


Binary Search

3 6 8 12 14 17 25 29 31 36 42 47 53 55 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Algorithm RBinarySearch(L, H, Key) T(n)


if (L == H)
if (A[L] == key)
return L; 1 1 n=1
else
return 0; T(n) =
else
𝒏
Mid = (L + H)/2; 1 T(𝟐) + 1 n>1
if (Key == A[Mid]) 1
return Mid;
if (Key < A[Mid]) 1 T(n) = 1 T( ) + 1
𝒏
return RBinarySearch(L, Mid-1,Key); 𝟐
𝒏 log 𝟐 𝟏 = 0
else T( )
𝟐 𝒏𝟎 O (log 𝒏)
return RBinarySearch(Mid+1,H,Key);
SaiviCodes © 2020 6/26/2020 18

You might also like