# First Position of Target

LintCode-14.First Position of Target

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge

If the count of numbers is bigger than 2^32, can your code work properly?

``````class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}

int low = 0, high = nums.length - 1;

while (low + 1 < high) {
int middle = low + (high - low) / 2;

if (nums[middle] == target) {
high = middle;
} else if (nums[middle] > target) {
high = middle;
} else {
low = middle;
}
}

if (nums[low] == target) {
return low;
}
if (nums[high] == target) {
return high;
}

return -1;
}
}
``````

Hope this helps,
Michael