LeetCode (14) Binary Search

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

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

Have you met this question in a real interview? 

Yes

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?

Tags Expand  

Related Problems Expand 

其实九章最有用的算是他的模板了。。。。当然最SB的也还是他的模板。。。以前B Search闭着眼都能写，现在还得想想， 模板如下：

1 while beg+1<end (最后是beg,end相邻）

2 mid= beg+(end-beg)/2 装B用的，为了防止int overflow

3 比较元素mid位置， beg=mid, end=mid 等等

4.如果求第一个，判断beg，如果求最后返回end,要么为1...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: /** * @param nums: The integer array. * @param target: Target number to find. * @return: The first position of target. Position starts from 0. */ int binarySearch(vector<int> &array, int target) { int beg=0; int end=array.size()-1; while(beg+1<end){ int mid=beg+(end-beg)/2; if (array[mid]<target){ beg=mid; } else{ end=mid; } } if (array[beg]==target) return beg; if (array[end]==target) return end; return -1; } };