Scribd
Upload
14 views

2 Wk10 Binary - Search - Lecture

Uploaded by

eddieldavies
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
14 views

2 Wk10 Binary - Search - Lecture

Uploaded by

eddieldavies
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/ 38

Binary Search

Dr Rob Blair
r.blair@uea.ac.uk SCI 2.19

1
Objectives
introduce a divide and conquer technique

understand how to exploit knowledge of the data

2
Binary Search Specification

return true if key is in array of values, else false

3
Binary Search Inputs

array of n values, sorted in non-descending order

element key

4
Binary Search Outputs

boolean - true if key found, else false

5
Binary Search Description

1.Compare key with the middle element.


2.If key matches with middle element, we return true.
3.Else if key is greater than the mid element, search right half.
4.Else (key is smaller) search left half.

6
4 9 9 10 12 15 22 23 24 27

7
10

4 9 9 10 12 15 22 23 24 27

8
10

4 9 9 10 12 15 22 23 24 27

9
10

4 9 9 10 12 15 22 23 24 27

10
10

4 9 9 10 12

11
10

4 9 9 10 12

12
10

4 9 9 10 12

13
10

10 12

14
10

10 12

15
10

16
Pseudo Code

17
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
18
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
19
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
20
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
21
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
22
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
23
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
24
Binary Search Recursive

25
bin_search(key, values, start, end):

if start > end:


return false

mid := (start + end) / 2


if key == values[mid]:
return true

if key < values[mid]:


return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
26
bin_search(key, values, start, end):

if start > end:


return false

mid := (start + end) / 2


if key == values[mid]:
return true

if key < values[mid]:


return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
27
bin_search(key, values, start, end):

if start > end:


return false

mid := (start + end) / 2


if key == values[mid]:
return true

if key < values[mid]:


return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
28
bin_search(key, values, start, end):

if start > end:


return false

mid := (start + end) / 2


if key == values[mid]:
return true

if key < values[mid]:


return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
29
bin_search(key, values, start, end):

if start > end:


return false

mid := (start + end) / 2


if key == values[mid]:
return true

if key < values[mid]:


return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
30
Time Complexity

31
Time Complexity

n
1= x
2

32
Time Complexity

x
2 =n

33
Time Complexity

x
log2(2 ) = log2(n)

34
Time Complexity
x
log2(2 ) = log2(n)
x × log2(2) = log2(n)

35
Time Complexity
x
log2(2 ) = log2(n)
x × log2(2) = log2(n)
x = log2(n)

36
Time Complexity

(log2(n))
𝒪
37
Time Complexity

same for recursive and iterative methods


just a choice of implementation...

38

You might also like