First Position of Target

Description

For a given sorted array (ascending order) and atargetnumber, find the first index of this number inO(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?

Related problems

Easy Closest Number in Sorted Array

Easy Last Position of Target

Easy Classical Binary Search

Medium Search in a Big Sorted Array

Medium Unique Binary Search Trees

Easy Sqrt(x)

Medium Search Range in Binary Search Tree

Implementation

Link: http://lintcode.com/en/problem/strstr/

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.length == 0) {
            return -1;
        } else {
            int first = 0; 
            int last = nums.length-1;
            while (first + 1 < last) {
                int mid = first + (last-first)/2;
                if (target == nums[mid]){
                    last  = mid;
                } else if (target < nums[mid]) {
                    last = mid;
                } else{
                    first = mid;
                }
            }
            if (nums[first] == target) {
                return first;
            }
            if (nums[last] == target) {
                return last;
            }
            return -1;
        }
    }
}