14.First Position of Target-二分查找（容易题）

二分查找

题目

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

样例

在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

挑战

如果数组中的整数个数超过了2^32，你的算法是否会出错？

题解

1、二分查找到第一个target后使用逐个向前查询第一个target

class Solution { /** * @param nums: The integer array. * @param target: Target to find. * @return: The first position of target. Position starts from 0. */ public int binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int low = 0; int high = nums.length - 1; while (low <= high) { //这里为了防止溢出，不可以写成int mid = (low + high) / 2; int mid = low + (high - low) / 2; if (nums[mid] == target) { int r = nums[mid]; //向前查找第一个target while (--mid >= 0 && nums[mid] == r); return ++mid;//补偿最后一次的--mid操作 } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } }

2、全程使用二分查找

class Solution { /** * @param nums: The integer array. * @param target: Target to find. * @return: The first position of target. Position starts from 0. */ public int binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0, end = nums.length - 1; while (start < end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { end = mid; } else if (nums[mid] < target) { start = mid + 1; } else { end = mid - 1; } } //当start==end的情况 if (nums[start] == target) { return start; } return -1; } }

Last Update 2016.8.16