Classical Binary Search

Classical Binary Search.png

===================== 解題思路 =====================

基本的二分法搜尋 找到 A[mid] = target 則回傳 否則 return -1

===================== C++ code ====================

<pre><code>
class Solution {

public:

/**
 * @param A an integer array sorted in ascending order
 * @param target an integer
 * @return an integer
 */
int findPosition(vector<int>& A, int target) {
    // Write your code here
    if(A.size() == 0) return -1;
    int left = 0, right = A.size() -1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(A[mid] == target) return mid;
        if(A[mid] > target) right = mid;
        else left = mid;
    }
    return -1;
}

};
<code><pre>