Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L36
Day 4 Introduction to Algorithms L3.6 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L3.7
Day 4 Introduction to Algorithms L3.7 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L3.8
Day 4 Introduction to Algorithms L3.8 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms
Day 4 Introduction to Algorithms L3.9 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial