CP114 Lecture Notes - Lecture 4: Binary Search Algorithm, Data Element, Linear Search
Document Summary
This means it must find the first occurrence of a series of equal values. The position of those values must be preserved by the list sort. One version of binary search performs two comparisons (greater than and less than) with respect to the midpoint. If both those comparisons fail, the key value and the midpoint value must be equal. However, there is no guarantee that the value found this way is the first in the list with that value. i = -1 low = 0. # index of end of subarray to search. high = len( self. _values ) - 1 while low < high and i = -1: # (avoids overflow on large values vs (low + high) // 2 mid = ( high - low ) // 2 + low if self. _values[mid] > key: # search the left subarray. high = mid - 1 elif self. _values[mid] < key: # value has been found. i = mid return i.
