//标准二分查找的模板
class BinarySearch {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) return mid;
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
- 循环中包含right == left 的情况所以每次都要改变left,right的值
- 因为是(left + right) >> 1 ,所以对于偶数个数的来说,mid总是偏左的,当指针相遇的时候,只会是一下两种情况
- left/mid , right right在后面一个,left/mid先相遇
- left/mid/right 指向同一个