Classical Binary Search模板式解法

describtion： Find any position of a target number in a sorted array. Return -1 if target does not exist.

Have you met this question in a real interview? Yes 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.

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) { // Write your code here if (nums == null || nums.length == 0) { return -1; } int lo = 0; int hi = nums.length - 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (target == nums[mid]) { return mid; } else if (target < nums[mid]) { hi = mid; } else { lo = mid; } } if (target == nums[lo]) { return lo; } if (target == nums[hi]) { return hi; } return -1; } }

直接使用二分法模板

lo + 1 < hi mid = lo + (hi - lo) / 2 mid < > == target Arr[lo]Arr[hi] ? target

总结成口诀

相邻就退出mid取中间三种关系式算好来比较