> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/first_position_of_target.md).

# First Position of Target

**Easy** 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.

## Thoughts

最基本的bin search问题。用STL中lower\_bound的实现方法找出数组中第一个和target相等或比target大的数(当target不在时)所在的index, 即最后start/end(它们俩最后相等)所在位置.

基于此思想把模板拓展成找第一个分界点(后半边第一个元素)所在位置. 当end == nums.len时分界点看成可以是非数组内元素, 否则是在nums里. 当落在分界点前时, 把对应的start/end移到mid并加一.

## Code

```
    /**
     * @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) {
        int start = 0, end = nums.length - 1;
        // 防止陷入死循环
        while (start < end) {
            // 这么写是为了防止越界
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return end > 0 ? -1 : nums[end] == target ? start : -1;
    }
```

## Analysis

Time Complexity: O(lgn)