本文主要是介绍Classical Binary Search,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Find any position of a target number in a sorted array. Return -1
if target does not exist.
Example
Example 1:
Input: nums = [1,2,2,4,5,5], target = 2
Output: 1 or 2
Example 2:
Input: nums = [1,2,2,4,5,5], target = 6
Output: -1
Challenge
O(logn) time
思路:经典算法,按照九章的模板来写;
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 { // nums[mid] > target;end = mid;}}if(nums[start] == target) {return start;}if(nums[end] == target) {return end;}return -1;}
}
这篇关于Classical Binary Search的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!