查找算法的比较 策略 一 -步数与n成正比 一称为线性时间算法 策略二 - 步数与log2n成正比 一称为对数时间算法 0 猜数游戏中：若数的范围是1~1000000，则 -策略一：平均要猜50万次才能猜对 人最坏1百万次，最好1次 -策略二：最坏也只需猜20次 Lu Chaojun,SJTU 6
Lu Chaojun, SJTU 6 查找算法的比较 • 策略一 – 步数与n成正比 – 称为线性时间算法 • 策略二 – 步数与log2 n成正比 – 称为对数时间算法 • 猜数游戏中:若数的范围是1~1000000,则 – 策略一:平均要猜50万次才能猜对 ©最坏1百万次,最好1次 – 策略二:最坏也只需猜20次
递归定义 ·两分查找算法的另一表述： 算法oinarySearch:在nums[low]~nums[high]中查找x mid (low high)/2 if low high x不在nums中 elif x nums [mid] 在nums[low]~nums[mid-1]中查找x else 在nums[mid+1]~nums[high]中查找x ·大问题的子问题仍是同样形式的问题，故 仍用解决大问题的算法来解决子问题 Lu Chaojun,SJTU 7
递归定义 • 两分查找算法的另一表述: 算法binarySearch:在nums[low]~nums[high]中查找x mid = (low + high) / 2 if low > high x 不在nums中 elif x < nums[mid] 在nums[low]~nums[mid-1]中查找x else 在nums[mid+1]~nums[high]中查找x • 大问题的子问题仍是同样形式的问题,故 仍用解决大问题的算法来解决子问题. Lu Chaojun, SJTU 7