排序数组中的搜索问题，首先想到 二分法 解决，本篇详细解析关于二分法边界的问题。

目录

一、二分法概念

二、剑指Offer53.在排序数组中查找数字

 三、在排序数组中查找元素的第一个和最后一个位置

一、二分法概念

二分法就是在一个有序递增的数组中进行折半查找。

如果中间的数字大于目标值，则right = middle - 1，全部排除

如果中间的数字小于目标值，则left = middle + 1，全部排除

普通写法：

int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
{int left = 0;int right = size - 1;	// 定义了target在左闭右闭的区间内，[left, right]while (left <= right) {	//当left == right时，区间[left, right]仍然有效int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出if (nums[middle] > target) {right = middle - 1;	//target在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1;	//target在右区间，所以[middle + 1, right]} else {	//既不在左边，也不在右边，那就是找到答案了return middle;}}//没有找到目标值return -1;
}

循环条件要使用while(left<=right)因为当(left == right)这种情况发生的时候，得到的结果是有意义的,切记千万不要写成left

二、剑指Offer53.在排序数组中查找数字

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）

统计一个数字在排序数组中出现的次数。

思路：在排序数组中的所有数字形成一个窗口，记录左边界和右边界，由于数组 nums 中元素都为整数，因此可以分别二分查找 target 和 target−1 的右边界，将两结果相减并返回即可。

class Solution {public int search(int[] nums, int target) {return helper(nums,target)-helper(nums, target-1);}public int helper(int[] nums,int target){int i = 0,j = nums.length-1;while (i <= j){int m = (i+j) / 2;if (nums[m] <= target){i = m+1;}else {j = m-1;}}return i;}
}

在寻找边界的过程中，如果将if(nums[m] < target)就变成了求左边界。

public int helper2(int[] nums,int target){int i = 0,j = nums.length-1;while (i <= j){int m = (i+j) / 2;if (nums[m] < target){i = m+1;}else {j = m-1;}}return j;}

 三、在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 题解 - 力扣（LeetCode）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 思路：分别找到target的右边界和target-1的右边界，然后将target-1的边界-1放进int[]数组中输出，随后return

class Solution {public int[] searchRange(int[] nums, int target) {int[] res = new int[] {-1, -1};int a = helper(nums,target-1);int b = helper(nums,target);if(b - a > 0){return new int[]{a,b-1};}return res;}int helper(int[] nums,int target){int i = 0,j = nums.length-1;while (i <= j){int m = i + (j-i) / 2;if (nums[m] <= target){i = m+1;}else {j = m-1;}}return i;}
}

分享一下心酸历史：