14 二分查找

原题网址：http://www.lintcode.com/zh-cn/problem/first-position-of-target/

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

挑战 

如果数组中的整数个数超过了2^32，你的算法是否会出错？

标签 

二分法 数组

 

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;


int binarySearch(vector<int> &nums, int target)
{
    if (nums.empty())
    {
        return -1;
    }
    int size=nums.size();
    if (target<nums[0]||target>nums[size-1])
    {
        return -1;
    }
    
    int max=size-1,min=0,mid=(max+min)/2;
    while(min<=max)
    {
        if (target==nums[mid])
        {
            for (int i=0;i<=mid;i++)
            {
                if (nums[i]==nums[mid])
                {
                    return i;
                }
            }
        }
        else if (target<nums[mid])
        {
            max=mid-1;
        }
        else
        {
            min=mid+1;
        }
        mid=(max+min)/2;
    }
    return -1;
}