Lintcode457 Classical Binary Sea

【题目描述】

Find any position of a target number in a sorted array. Return -1 if target does not exist.

在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1

【题目链接】

www.lintcode.com/en/problem/classical-binary-search/

【题目解析】

题目是求目标值在数组中的位置。考查Binary Search基本的实现写法。

标准的Binary Search的实现过程一般按下面步骤：

检查数列合理性是否为null或者为空

初始化Binary Search所需的首尾index索引变量start和end。start = 0， end ＝ 数组长度 – 1。

通过一个条件为start + 1 < end的while循环来不断二分减小搜索区间，设置中间索引变量mid = start + (end – start) / 2。如果数列在mid索引位置的值不等于搜索的目标值，则继续循环。每次循环中需要更新mid索引的值。直到搜索的区间只剩下相邻两个数。

while循环过后只剩下相邻两个数。和目标值比较。如果仍旧没有找到，则返回-1。

【参考答案】

www.jiuzhang.com/solutions/classical-binary-search/