First position of Target.png
===================== 解題思路 =====================
BS 方式尋找到 target, 但是這次可能會(huì)有重複的數(shù)字存在 所以需要找到的是index 最小的target 位置 所以在找到 target 之後並不中斷 loop, 繼續(xù)壓縮範(fàn)圍往 target 集中 最後在 while loop 設(shè)定的條件下結(jié)束時(shí) 照順序檢查 left 跟 right 是否為 target (left 優(yōu)先) 如果都沒(méi)有回傳 -1
===================== C++ code ====================
<pre><code>
class Solution {
public:
/**
* @param nums: The integer array.
* @param target: Target number to find.
* @return: The first position of target. Position starts from 0.
*/
int binarySearch(vector<int> &array, int target) {
// write your code here
int left = 0, right = array.size() - 1;
while(left + 1 < right)
{
int mid = left + (right - left) / 2;
if(array[mid] >= target) right = mid;
else left = mid;
}
if(array[left] == target) return left;
if(array[right] == target) return right;
return -1;
}
};
<code><pre>
