LintCode 457. Classical Binary Search 原创Java参考解答

问题描述

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

解题思路

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

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

1. 检查数列合理性是否为null或者为空
2. 初始化Binary Search所需的首尾index索引变量start和end。start = 0， end ＝ 数组长度 – 1。
3. 通过一个条件为start + 1 < end的while循环来不断二分减小搜索区间，设置中间索引变量mid = start + (end – start) / 2。如果数列在mid索引位置的值不等于搜索的目标值，则继续循环。每次循环中需要更新mid索引的值。直到搜索的区间只剩下相邻两个数。
4. 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; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总