Binary SearchSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966Binary SearchloBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.hiBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lohimidBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lohiBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lomid hiBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lo hiBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lo himidBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lohiBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95 97966lohimidBinary SearchBinary search. Given value and sorted array a[], find index isuch that a[i] = value, or report that no such index exists.Invariant. Algorithm maintains a[lo] value a[hi].Ex. Binary search for 33.821 3 4 65 7 109 11 12 14130641413 25 33 5143 53 8472 93 95
View Full Document
Unlocking...