Teach Binary Search Algorithm with example

Binay search algorithm teaching

1. Binary Search Algorithm

2. Searching

3. What is searching ? Searching is a process used to find the location of a target among a list of objects. e.g., where is 1 4 ?

4. Successful searching in an unordered list

5. Unsuccessful search in unordered list

6. Search Algorithms 6

7. Binary Search O(log2 n) A binary search looks for an item in a list using a divide-and-conquer strategy 7

8. Binary Search Binary search algorithm assumes that the items in the array being searched are sorted We start by dividing the array into 2 parts and look look for the item in the middle of the array in a binary search If the item we are searching is less than the item in the middle , we know that the item won’t be in the second half of the array. So we look in the 1 st half Once again we examine the middle element The process continues with each comparison cutting in half the portion of the array until we reach the location the item might be

9. Determine whether 22 is in the list Binary Search Algorithm Example Array list with twelve (12) elements 21 is less than 22, so we look in the 2 nd half

10. Binary Search Algorithm (Cont’d) Search list, list[6] … list[11] first = mid + 1

11. Binary search example 11 Mid =(6+11)/2 =8

12. Unsuccessful binary search example 12

13. Binary Search 13

14. Binary Search 14

15. 15