Lintcode14 First Position of Target Solution problem solution

[topic description]

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.

Given a sorted array of integers (ascending order) and an integer target to find, use O (logn) time to find the first subscript of target (starting at 0), and return-1 if target does not exist in the array.

[topic link]

Http://www.lintcode.com/en/problem/first-position-of-target/

[topic Analysis]

This topic requires the complexity of O (logn), which is sorted array again, so let's do dichotomy without saying much. Note that first position of target is required, so when (array [mid] = = target), the operation is end = mid.

After finding the first target in dichotomy, query the first target one by one

Use binary search in the whole process.

[answer link]

Http://www.jiuzhang.com/solutions/first-position-of-target/