二分查找基本算法
用于查找已排列数组,且一般没有重复数
左闭右开
查找区间为 [ Left , Right ) ,比较Left和Right中间的那个数和Target的。如果中间数大于target,将Left设为Middle-1;如果中间数小于target,将Right设为Middle。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;//因为是左开右闭,[Left,Right)
while (left < right) {// 因为left == right的时候,在[left, right)是无效的空间
int mid = left + ((right - left) / 2);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
}
左闭右闭
查找区间为 [ Left , Right ] ,比较Left和Right中间的那个数和Target的。如果中间数大于target,将Left设为Middle-1;如果中间数小于target,将Right设为Middle+1。
public int search(int[] nums, int target) {
int Left = 0; // 左初始化为最左边一格
int Right = nums.length - 1; // 左初始化为最右边一格
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (target < nums[Left] || target > nums[Right])
return -1;
while (Left <= Right) {
int Middle = Left + (Right - Left) / 2;
if (nums[Middle] < target)
Left = Middle + 1;
else if (nums[Middle] > target)
Right = Middle - 1;
else
return Middle;
}
return -1;
}
此外,观察到如果target不在数组里。循环结束后,Left是比这个数大的数里最小的,Right是比这个数小的数里最大的
在排序数组中查找元素的第一个和最后一个位置
题目:
给你一个按照非递减顺序排列的整数数组
nums
,和一个目标值target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值target
,返回[-1, -1]
。
可以通过两次二分查找(左闭右闭),分别查找左边界和有边界。先设左右边界为-1,若寻找到target再赋其他值。左边界既先找到等于目标的数并假令左边界为这个数,再令Right=Middle-1 继续寻找左边是否依然有等于target的数。右边界寻找同理。
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int LeftSearch = -1;
int RightSearch = -1;
// 计算左边界(既:二分查找找到最左边的等于target的数)
while (left <= right) {
int midle = left + (right - left) / 2;
if (nums[midle] < target) {
left = midle + 1;
} else if (nums[midle] > target) {
right = midle - 1;
} else if (nums[midle] == target) {
/* 若匹配到target,先假令第一个数等于middle
再查找左半边有没有依然等于target的 */
LeftSearch = midle;
right = midle - 1;
}
}
//
left = 0;
right = nums.length - 1;
// 计算右边界(既:二分查找找到最右边的等于target的数)
while (left <= right) {
int midle = left + (right - left) / 2;
if (nums[midle] < target) {
left = midle + 1;
} else if (nums[midle] > target) {
right = midle - 1;
} else if (nums[midle] == target) {
/*若匹配到target,先假令最后一个数等于middle
再查找右半边有没有依然等于target的*/
RightSearch = midle;
left = midle + 1;
}
}
return new int[] { LeftSearch, RightSearch };
}
标签:二分,Right,java,target,nums,int,查找,right,left
From: https://www.cnblogs.com/alienus/p/17926885.html