找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 41|回复: 0

[代码与实例] Lintcode457 Classical Binary Search solution 题解

10

主题

10

帖子

10

积分

贫民

积分
10
Jenny 发表于 2018-6-12 21:42:30 | 显示全部楼层 |阅读模式
【题目描述】
Find any position of a target number in a sorted array. Return -1 if target does not exist.
在一个排序数组中找一个数,返回该数出现的任意位置,如果不存在,返回-1

【题目解析】
题目是求目标值在数组中的位置。考查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。



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表