面試四： 查找排序

    面試官還問了我另外一個問題，就是給我一個嚴格遞增或是嚴格遞減的數組，讓我将裡面的某個資料取出來，這不就是折半查找嗎？

    下面我就整理一下二分查找：

    算法複雜度：折半搜尋每次把搜尋區域減少一半，時間複雜度為。（n代表集合中元素的個數）

    問題描述：有一個按非降序排列的有序數組a[0...n-1]和一個數v

    1.求數組a中最後一次出現的數key的下标

    設l為左邊界，h為右邊界，mid

= (l+h)/2，那麼，根據mid的取值，分三種情況:

    (1)

a[mid] < key，說明v如果在數組中，應該出現在mid右側，則調整左邊界，l

= mid + 1

    (2)

a[mid] > key，說明v如果在數組中，應該出現在mid左側，則調整右邊界，h

= mid - 1

    (3)

a[mid] ==key，中間值等于key，而要求的是最後一次出現的key。最後出現的v值一定在mid的右邊或者就是mid位置的這個值，是以我們應該調整左邊界，l

= mid。

    java實作：