LintCode 457. Classical Binary Search 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/classical-binary-search/
Find any position of a target number in a sorted array. Return -1 if target does not exist.
Example
Given [1, 2, 2, 4, 5, 5]
.
For target = 2
, return 1 or 2.
For target = 5
, return 4 or 5.
For target = 6
, return -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。
参考代码
public class Solution { /** * @param nums: An integer array sorted in ascending order * @param target: An integer * @return an integer */ public int findPosition(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] == target) { return start; } if (nums[end] == target) { return end; } return -1; } }