#|leetcode之二分查找算法(升序数组)（闭合区间下解决查找单个元素、左右侧边界元素） #|算法

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/
做了几个leetcode题，发现查找单个元素、左右侧边界元素的代码不一样，有时候mid 加一还是减一，while 里到底用 <= 还是 <,这个很烦。
我就用mid加一和减一，<= 三种方式查找：单个元素、左侧元素、右侧元素
【#|leetcode之二分查找算法(升序数组)（闭合区间下解决查找单个元素、左右侧边界元素）】二分法查找数组一定要是升序的数组
思路分析：

第一个，最基本的二分查找算法：因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1 因为我们只需找到一个 target 的索引即可所以当 nums[mid] == target 时可以立即返回

第二个，寻找左侧边界的二分查找：因为我们初始化 right = nums.length 所以决定了我们的「搜索区间」是 [left, right) 所以决定了 while (left < =right) 同时也决定了 left = mid + 1 和 right = mid因为我们需找到 target 的最左侧索引所以当 nums[mid] == target 时不要立即返回而要收紧右侧边界以锁定左侧边界,right=mid-1,不断减小下界

第三个，寻找右侧边界的二分查找：因为我们初始化 right = nums.length 所以决定了我们的「搜索区间」是 [left, right) 所以决定了 while (left <= right) 同时也决定了 left = mid + 1 和 right = mid因为我们需找到 target 的最右侧索引所以当 nums[mid] == target 时不要立即返回而要收紧左侧边界以锁定右侧边界,left=mid+1,不断增大上界又因为收紧左侧边界时必须 left = mid + 1 所以最后无论返回 left 还是 right，必须减一

对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的「搜索区间」，我们还根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：

//查找单个元素 int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; } //左边界查找元素 int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，收缩左侧边界 right = mid - 1; } } // 最后要检查 left 越界的情况 if (left >= nums.length || nums[left] != target) return -1; return left; }//右边界查找元素 int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，收缩右侧边界 left = mid + 1; } } // 最后要检查 right 越界的情况 if (right < 0 || nums[right] != target) return -1; return right; }

力抠33 单个元素查找的变形：分段升序二分查找

package _033搜索旋转排序数组; /** *假设按照升序排序的数组在预先未知的某个点上进行了旋转。 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 * 你可以假设数组中不存在重复的元素。 * 你的算法时间复杂度必须是 O(log n) 级别。 * 示例 1: * 输入: nums = [4,5,6,7,0,1,2], target = 0 * 输出: 4 * 示例 2: * 输入: nums = [4,5,6,7,0,1,2], target = 3 * 输出: -1 * */ //二分查找 public class Solution { public int search(int[] nums, int target) { if(nums==null||nums.length==0) return -1; int left=0,right=nums.length-1; while (left<=right){//循环条件：只要left<=right,就一直循环。 int mid=(left+right)/2; //找到就返回 if (nums[mid]==target) return mid; //先判断左半端，左半端是升序，右半段是降序，所以在左半端升序用二分查找 if (nums[left]<=nums[mid]){ //里面继续用二分查找的左右下标 if(target>=nums[left]&&targetnums[mid]){ left=mid+1; }else { right=mid-1; } } } return -1; } }

力扣34 左右侧边界元素查找

package _034在排序数组中查找元素的第一个和最后一个位置; /** * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。 * 找出给定目标值在数组中的开始位置和结束位置。 * 你的算法时间复杂度必须是 O(log n) 级别。 * 如果数组中不存在目标值，返回 [-1, -1]。 * * 示例 1: * 输入: nums = [5,7,7,8,8,10], target = 8 * 输出: [3,4] * 示例 2: * 输入: nums = [5,7,7,8,8,10], target = 6 * 输出: [-1,-1] * */ class Solution { public int[] searchRange(int[] nums, int target) { if(nums==null||nums.length==0) return new int[]{-1,-1}; //寻找左侧边界的二分查找 int left=left_search(nums,target); //寻找右侧边界的二分查找 int right=right_search(nums,target); return new int[]{left,right}; } //找左边界是不断的往左压缩，左右界一起动，直到left>=nums.lengh public int left_search(int[] nums,int target){ int left=0,right=nums.length-1; while(left <= right){ int mid = (left + right)/2; //这个一定要写里面 if (nums[mid]target){ right=mid-1; }else if (nums[mid]==target){//当找到点时不要急着返回，而是让他往左边压缩，找到左侧边界，所以下界不断减小； right=mid-1; } } if(left >=nums.length||nums[left]!=target){ //注意处理下标越界的情况，如果target比nums数组的值要大，则越界 return -1; } return left; //找到左边界 } //找右边界是不断的往右压缩，左右界一起动，直到right<0 public int right_search(int[] nums,int target){ int left=0,right=nums.length-1; while (left<=right){ int mid=(left+right)/2; if (nums[mid]target){ right=mid-1; }else if (nums[mid]==target){//当找到点时不要急着返回，而是让他往右边压缩，找到右侧边界，所以上界不断增大； left=mid+1; } } if (right<0||nums[right]!=target){return -1; }//越界检查，当target比nums值都小时，越界 return right; } }