申論題

有個矩陣A[1..n]，n的值很大。在矩陣A中存有n個正整數，且從小到大排列。給定 某個整數x，二分搜尋法（binary search）可以在O(log n)的時間內找出x在矩陣 A[1..n]的位置，或宣告在A[1..n]中沒有x。在某個應用中，已知絕大部分的x都會出 現在矩陣a[1..n]的前面m個元素，且 m 的值遠小於n，但是無法預知m的範圍。設 計一個演算法，可以在O(log m)的時間內完成搜尋。（20分）