Discrete Mathematics Lecture 5 PDF

Discrete Mathematics Lecture 05 Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2025  Chapter 4: Number Theory The Integers and Division. Integer Representations. Primes...

Discrete Mathematics Lecture 05 Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2025  Chapter 4: Number Theory The Integers and Division. Integer Representations. Primes. Greatest Common Divisors. Least Common Multiple. ©Ahmed Hagag Discrete Mathematics 2  Division (1/15) DEFINITION 𝑏 (or equivalently, if is an integer) 𝑎 ©Ahmed Hagag Discrete Mathematics 3  Division (1/15) DEFINITION Remark: We can express 𝑎 ∣ 𝑏 using quantifiers as ∃𝑐(𝑎𝑐 = 𝑏), where the universe of discourse is the set of integers. ©Ahmed Hagag Discrete Mathematics 4  Division (2/15) Example 1 ©Ahmed Hagag Discrete Mathematics 5  Division (2/15) Example 1 – Solution ©Ahmed Hagag Discrete Mathematics 6  Division (3/15) Example 2 A number line indicates which integers are divisible by the positive integer 𝑑. which integers are divisible by the positive integer 𝒅. ©Ahmed Hagag Discrete Mathematics 7  Division (4/15) Example 3 Let 𝑛 and 𝑑 be positive integers. How many positive integers not exceeding 𝑛 are divisible by 𝑑? The positive integers divisible by 𝑑 are all the integers of the form 𝑑𝑘, where 𝑘 is a positive integer. Hence, the number of positive integers divisible by 𝑑 that do not exceed 𝑛 equals the number of integers 𝑘 with 0 < 𝑑𝑘 ≤ 𝑛, or with 0 < 𝑘 ≤ 𝑛/𝑑. Therefore, there are 𝒏/𝒅 positive integers not exceeding 𝑛 that are divisible by 𝑑. ©Ahmed Hagag Discrete Mathematics 8  Division (5/15) THEOREM 𝐋𝐞𝐭 𝒂, 𝒃, 𝐚𝐧𝐝 𝒄 𝐛𝐞 𝐢𝐧𝐭𝐞𝐠𝐞𝐫𝐬, 𝐰𝐡𝐞𝐫𝐞 𝒂 ≠ 𝟎. 𝐓𝐡𝐞𝐧 𝑖 if 𝑎 𝑏 and 𝑎 𝑐, then 𝑎 | 𝑏 + 𝑐 𝑖𝑖 if 𝑎 𝑏, then 𝑎 𝑏𝑐 for all integers 𝑐 𝑖𝑖𝑖 if 𝑎 𝑏 and 𝑏 𝑐, then 𝑎 | 𝑐 𝐀𝐬 𝐚 𝐫𝐞𝐬𝐮𝐥𝐭: If 𝑎 𝑏 and 𝑎 𝑐, then 𝑎 | 𝒎𝑏 + 𝒏𝑐 whenever 𝒎 and 𝒏 are integers ©Ahmed Hagag Discrete Mathematics 9  Division (6/15) Examples 1) Does 2 divdes 4? 2) Does 2 divdes 8? 3) 2 divdes 4 + 8 ? 4) Does 2 divdes 4? 5) Does 2 divdes 4 ∗ 5? 6) Does 2 divdes 4 ∗ 4? 7) Does 2 divdes 4? 8) Does 4 divdes 16? 9) Does 2 divdes 16? ©Ahmed Hagag Discrete Mathematics 10  Division (7/15) The Division Algorithm Let 𝒂 be an integer and 𝒅 a positive integer. Then dividend 𝑎 = 𝑞𝑢𝑜𝑡𝑖𝑒𝑛𝑡 𝑞 , 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 𝑟 𝑑 divisor 𝑤𝑖𝑡ℎ , 0≤𝑟 1, we see that 10, 19, and 24 are not pairwise relatively prime. ©Ahmed Hagag Discrete Mathematics 61  Least Common Multiple (1/5) DEFINITION “𝐥𝐜𝐦” ©Ahmed Hagag Discrete Mathematics 62  Least Common Multiple (2/5) Example 1 What is the lcm 24, 36 ? 24 are 2, 3 36 are 2, 3, 5 24 2 36 2 12 2 18 2 6 2 9 3 3 = 23 ∙ 3 3 = 22 ∙ 32 3 3 1 1 lcm 24,36 = 23 ∙ 32 = 72 ©Ahmed Hagag Discrete Mathematics 63  Least Common Multiple (3/5) Example 2 What is the lcm 120, 500 ? 120 are 2, 3,5,7 500 are 2, 3, 5,7,11,13,17,19 120 2 500 2 60 2 250 2 30 2 125 5 15 3 = 23 ∙ 3 ∙ 5 25 5 = 22 ∙ 53 5 5 5 1 5 1 lcm 120, 500 = 23 ∙ 31 ∙ 53 = 3000 ©Ahmed Hagag Discrete Mathematics 64  Least Common Multiple (4/5) THEOREM Let 𝑎 and 𝑏 be positive integers. Then 𝑎𝑏 = gcd(𝑎, 𝑏) ⋅ lcm(𝑎, 𝑏) ©Ahmed Hagag Discrete Mathematics 65  Least Common Multiple (5/5) Example 3 What are the 𝐠𝐜𝐝 𝟏𝟐𝟎, 𝟓𝟎𝟎 and 𝐥𝐜𝐦 𝟏𝟐𝟎, 𝟓𝟎𝟎 ? 120 are 2, 3,5,7 500 are 2, 3, 5,7,11,13,17,19 120 2 500 2 60 2 250 2 30 2 125 5 15 3 = 23 ∙ 3 ∙ 5 25 5 = 22 ∙ 53 5 5 5 1 5 1 lcm 120, 500 = 23 ∙ 31 ∙ 53 = 3000 120 ∗ 500 gcd 120, 500 = = 20 3000 ©Ahmed Hagag Discrete Mathematics 66  Applications (1/4) 1. Hashing Functions 2. Pseudorandom Numbers 3. Cryptography … ©Ahmed Hagag Discrete Mathematics 67  Applications (2/4) 1. Hashing Functions ©Ahmed Hagag Discrete Mathematics 68  Applications (3/4) 2. Pseudorandom Numbers linear congruential method ©Ahmed Hagag Discrete Mathematics 69  Applications (4/4) 𝑚 is the number Classical Cryptography of elements in the 3. Cryptography language used. Encryption 𝑘 is called a key Decryption ©Ahmed Hagag Discrete Mathematics 70  Searching Algorithms (10/18) Binary Search Algorithm This algorithm can be used when the list has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in alphabetic, order). It proceeds by comparing the target element to be located to the middle term of the list. The list is then split into two smaller sublists of the same size until to get the target element. ©Ahmed Hagag BS102 Discrete Mathematics 3  Searching Algorithms (10/18) Binary Search Algorithm This algorithm can be used when the list has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in alphabetic, order). It proceeds by comparing the target element to be located to the middle term of the list. The list is then split into two smaller sublists of the same size until to get the target element. ©Ahmed Hagag BS102 Discrete Mathematics 4  Searching Algorithms (11/18) Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 ©Ahmed Hagag BS102 Discrete Mathematics 5  Searching Algorithms (11/18) Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 ©Ahmed Hagag BS102 Discrete Mathematics 6  Searching Algorithms (11/18) Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 Value is founded in location 𝟓 return 5 ©Ahmed Hagag BS102 Discrete Mathematics 7  Searching Algorithms (12/18) Example 2 Locate an element 𝟐𝟓 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 ©Ahmed Hagag BS102 Discrete Mathematics 8  Searching Algorithms (12/18) Example 2 Locate an element 𝟐𝟓 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐯𝐚𝐥𝐮𝐞 𝐢𝐬 𝐧𝐨𝐭 𝐟𝐨𝐮𝐧𝐝 return 0 ©Ahmed Hagag BS102 Discrete Mathematics 9  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 𝐥𝐨𝐜𝐚𝐭𝐢𝐨𝐧 = 𝟏 𝐦𝐚𝐱 𝐥𝐨𝐜𝐚𝐭𝐢𝐨𝐧 = 𝟕 ©Ahmed Hagag BS102 Discrete Mathematics 10  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟕 ©Ahmed Hagag BS102 Discrete Mathematics 11  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟕 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟒 =𝟒 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 12  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟕 𝐦𝐢𝐝 = 𝟒 𝐓𝐚𝐫𝐠𝐞𝐭 𝟏𝟎 > 𝟗 ∴ 𝐦𝐢𝐧 = 𝐦𝐢𝐝 + 1 = 5 ©Ahmed Hagag BS102 Discrete Mathematics 13  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟓 𝐦𝐚𝐱 = 𝟕 ©Ahmed Hagag BS102 Discrete Mathematics 14  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟓 𝐦𝐚𝐱 = 𝟕 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟔 =𝟔 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 15  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟓 𝐦𝐚𝐱 = 𝟕 𝐦𝐢𝐝 = 𝟔 𝐓𝐚𝐫𝐠𝐞𝐭 𝟏𝟎 < 𝟏𝟒 ∴ 𝐦𝐚𝐱 = 𝐦𝐢𝐝 − 𝟏 = 𝟓 ©Ahmed Hagag BS102 Discrete Mathematics 16  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟓 𝐦𝐚𝐱 = 𝟓 𝐦𝐢𝐝 = 𝟓 ©Ahmed Hagag BS102 Discrete Mathematics 17  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟓 𝐦𝐚𝐱 = 𝟓 𝐦𝐢𝐝 = 𝟓 𝐓𝐚𝐫𝐠𝐞𝐭 𝟏𝟎 = 𝟏𝟎 ©Ahmed Hagag BS102 Discrete Mathematics 18  Searching Algorithms (13/18) Binary Search Algorithm (1) – Example 1 Locate an element 𝟏𝟎 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 2 5 7 9 10 14 20 𝐦𝐢𝐧 = 𝟓 𝐦𝐚𝐱 = 𝟓 Value is founded in location 𝟓 𝐦𝐢𝐝 = 𝟓 return 5 𝐓𝐚𝐫𝐠𝐞𝐭 𝟏𝟎 = 𝟏𝟎 ©Ahmed Hagag BS102 Discrete Mathematics 19  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐢𝐧 𝐥𝐨𝐜𝐚𝐭𝐢𝐨𝐧 = 𝟏 𝐦𝐚𝐱 𝐥𝐨𝐜𝐚𝐭𝐢𝐨𝐧 = 𝟔 ©Ahmed Hagag BS102 Discrete Mathematics 20  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟔 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟑. 𝟓 = 𝟑 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 21  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐢𝐧 = 𝟏 𝐦𝐢𝐝 = 𝟑 𝐦𝐚𝐱 = 𝟔 𝐓𝐚𝐫𝐠𝐞𝐭 𝟒 < 𝟕 ∴ 𝐦𝐚𝐱 = 𝐦𝐢𝐝 − 1 = 2 ©Ahmed Hagag BS102 Discrete Mathematics 22  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 23  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟐 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟏. 𝟓 = 𝟏 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 24  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟐 𝐦𝐢𝐝 = 𝟏 𝐓𝐚𝐫𝐠𝐞𝐭 𝟒 > 𝟐 ∴ 𝐦𝐢𝐧 = 𝐦𝐢𝐝 + 1 = 2 ©Ahmed Hagag BS102 Discrete Mathematics 25  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐚𝐱 = 𝟐 𝐦𝐢𝐧 = 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 26  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐚𝐱 = 𝟐 𝐦𝐢𝐧 = 𝟐 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟐 =𝟐 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 27  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐚𝐱 = 𝟐 𝐦𝐢𝐧 = 𝟐 𝐦𝐢𝐝 = 𝟐 𝐓𝐚𝐫𝐠𝐞𝐭 𝟒 < 𝟓 ∴ 𝐦𝐚𝐱 = 𝐦𝐢𝐝 − 𝟏 = 𝟏 ©Ahmed Hagag BS102 Discrete Mathematics 28  Searching Algorithms (14/18) Binary Search Algorithm (1) – Example 2 Locate an element 𝟒 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 2 5 7 9 10 14 𝐦𝐚𝐱 = 𝟏 𝐦𝐢𝐧 = 𝟐 𝐢𝐟 𝐦𝐚𝐱 < 𝐦𝐢𝐧 𝐒𝐭𝐨𝐩 and 𝐫𝐞𝐭𝐮𝐫𝐧 0 ©Ahmed Hagag BS102 Discrete Mathematics 29  Searching Algorithms (15/18) Binary Search Algorithm (1) 1. Let 𝑚𝑖𝑛 = 1 and 𝑚𝑎𝑥 = 𝑛. 2. If 𝑚𝑎𝑥 < 𝑚𝑖𝑛, then stop: target is not present in array. Return 0. 3. Compute guess as the average of max and min, rounded down (so that it is an integer). 4. If array[guess] equals target, then stop. Return guess. 5. If the guess was too low, that is, array[guess] < target, then set 𝑚𝑖𝑛 = guess + 1. 6. Otherwise, the guess was too high. Set 𝑚𝑎𝑥 = guess − 1. 7. Go back to step 2. ©Ahmed Hagag BS102 Discrete Mathematics 30  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 ©Ahmed Hagag BS102 Discrete Mathematics 31  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟏 𝐦𝐚𝐱 = 𝟏𝟎 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟓. 𝟓 = 𝟓 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 32  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟏 𝐦𝐢𝐝 = 𝟓 𝐦𝐚𝐱 = 𝟏𝟎 𝐓𝐚𝐫𝐠𝐞𝐭 𝟑𝟏 > 𝟐𝟕 ∴ 𝐦𝐢𝐧 = 𝐦𝐢𝐝 + 1 = 6 ©Ahmed Hagag BS102 Discrete Mathematics 33  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟔 𝐦𝐚𝐱 = 𝟏𝟎 ©Ahmed Hagag BS102 Discrete Mathematics 34  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟔 𝐦𝐚𝐱 = 𝟏𝟎 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟖 =𝟖 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 35  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟔 𝐦𝐚𝐱 = 𝟏𝟎 𝐦𝐢𝐝 = 𝟖 𝐓𝐚𝐫𝐠𝐞𝐭 𝟑𝟏 < 𝟑𝟓 ∴ 𝐦𝐚𝐱 = 𝐦𝐢𝐝 − 1 = 7 ©Ahmed Hagag BS102 Discrete Mathematics 36  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟔 𝐦𝐚𝐱 = 𝟕 ©Ahmed Hagag BS102 Discrete Mathematics 37  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐧 = 𝟔 𝐦𝐚𝐱 = 𝟕 𝐦𝐢𝐧 + 𝐦𝐚𝐱 𝐦𝐢𝐝 = = 𝟔. 𝟓 = 𝟔 𝟐 ©Ahmed Hagag BS102 Discrete Mathematics 38  Searching Algorithms (16/18) Binary Search Algorithm (1) – Example 3 Locate an element 𝟑𝟏 in this list Location 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝐦𝐢𝐝 = 𝟔 𝐓𝐚𝐫𝐠𝐞𝐭 𝟑𝟏 = 𝟑𝟏 Value is founded in location 𝟔 return 6 ©Ahmed Hagag BS102 Discrete Mathematics 39  Searching Algorithms (17/18) Binary Search Algorithm (2) ©Ahmed Hagag BS102 Discrete Mathematics 40  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 41  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 1 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 42  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 1 16 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 43  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 1 16 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 44  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 1 16 8 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 45  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 1 16 8 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 46  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 9 16 8 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 47  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 9 16 8 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 48  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 9 16 12 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 49  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 9 16 12 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 50  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 16 12 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 51  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 16 12 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 52  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 16 14 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 53  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 16 14 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 54  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 14 14 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 55  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 14 14 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 56  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 14 13 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 57  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 13 14 13 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 58  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 14 14 13 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 59  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 14 14 13 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 60  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 14 14 13 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 61  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 14 14 13 𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 ©Ahmed Hagag BS102 Discrete Mathematics 62  Searching Algorithms (18/18) Binary Search Algorithm (2) 𝑛 𝑥 𝑖 𝑗 𝑚 16 19 14 14 13 𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛 𝑖𝑛𝑑𝑒𝑥 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 𝟏𝟒 ©Ahmed Hagag BS102 Discrete Mathematics 63