力扣二分搜索的总结
文章目录
二分搜索总结
找目标数
有序数组（无重复元素）
力扣704
基本写法
class Solution {
public int binarySearch(int[] nums, int target) {
int l = 0, r = nums.length-1;
while(l <= r ){
//int mid = l + (r -l)/2;
int mid = l + (r -l >> 1);
if(nums[mid] == target){
return mid;
}
else if (nums[mid] < target){
l = mid + 1;
}
else {
r = mid - 1;
}
}
return -1;
}
}
力扣35
基本写法
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
while(l <= r){
int mid = l + (r-l >>2);
if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
l = mid+1;
}
else{
r = mid-1;
}
}
return l;
}
}
有序数组（元素可重复）
力扣34
返回第一个（最左）等于target的索引值， 返回最后一个（最右）等于target的索引值
public int binarySearchLeft(int[] nums, int target){
int l = 0, r = nums.length-1;
while(l <= r){
int mid = (l + r)>>>1;
if(nums[mid] == target){
if(mid == 0 || nums[mid-1] < target){
return mid;
}
r = mid - 1;
}
else if(nums[mid] > target){
r = mid - 1;
}
else{
l = mid + 1;
}
}
return -1;
}
public int binarySearchRight(int[] nums, int target){
int l = 0, r = nums.length-1;
while(l <= r){
int mid = (l + r)>>>1;
if(nums[mid] == target){
if(mid == nums.length-1 || nums[mid+1] > target){
return mid;
}
l = mid + 1;
}
else if(nums[mid] > target){
r = mid - 1;
}
else{
l = mid + 1;
}
}
return -1;
}
旋转数组（无重复元素）
力扣33
没有重复元素的部分有序数组，搜索旋转排序数组
自己写的
//自己写的
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length-1;
while(l <= r){
int mid = (l + r) >>> 1;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] > target){
//当l和r之间存在旋转点的时候，且target数值小于左指针的数值时，表示左指针到数组最大值都是无效的，其实这时候应该将l指向最小的那个数，但是无法做到，只能将l++，效率低了一些
if(nums[r] < nums[l] && target < nums[l]){
l++;
}
else{
r = mid - 1;
}
}
else{
//当l和r之间存在旋转点的时候，且target数值大于右指针的数值时，表示数组最小值到右指针所指的数都是无效的，其实这时候应该将r指向最大的那个数，但是无法做到，只能将r--，效率低了一些
if(nums[r] < nums[l] && target > nums[r]){
r--;
}
else{
l = mid + 1;
}
}
}
return -1;
}
}
别人的思路
//别人的思路
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
}
// 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段
if (nums[mid] >= nums[l]) {
// 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 l 和 r
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
力扣153
寻找旋转排序数组中的最小值 部分有序数组找最小值，不含重复元素
class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length-1;
while(l < r){
int mid = (r-l)/2+l;
if(nums[mid] < nums[r]){
r = mid;
}
else{
l = mid + 1;
}
}
return nums[r];
}
}
旋转数组（元素可重复）
力扣81
有重复元素的部分有序数组（旋转数组）
自己写的，只需要把nums[r] < nums[l] 改为 nums[r] <= nums[l]
//自己写的
class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length-1;
while(l <= r){
int mid = (l + r) >>> 1;
if(nums[mid] == target){
return true;
}
else if(nums[mid] > target){
//当l和r之间存在旋转点的时候，且target数值小于左指针的数值时，表示左指针到数组最大值都是无效的，其实这时候应该将l指向最小的那个数，但是无法做到，只能将l++，效率低了一些
if(nums[r] <= nums[l] && target < nums[l]){
l++;
}
else{
r = mid - 1;
}
}
else{
//当l和r之间存在旋转点的时候，且target数值大于右指针的数值时，表示数组最小值到右指针所指的数都是无效的，其实这时候应该将r指向最大的那个数，但是无法做到，只能将r--，效率低了一些
if(nums[r] <= nums[l] && target > nums[r]){
r--;
}
else{
l = mid + 1;
}
}
}
return false;
}
}
别人的思路，在上一个题的基础上，用一个if保证左指针指的数和mid指针指的数不相同，否则无法在后面判断mid在前半部分还是后半部分
//别人的思路
class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return true;
}
if(nums[l] == nums[mid]){
l++;
continue;
}
// 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段
if (nums[mid] > nums[l]) {
// 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 l 和 r
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return false;
}
}
力扣154
寻找旋转排序数组中的最小值 II，含有重复元素，和之前的处理方法一样
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length-1;
while(l < r){
int mid = l + (r - l >>1);
//r--不会错过最小值，因为mid在r前面，两个的值相等,保证后序能判断mid是属于左部分还是右部分
if(nums[mid] == nums[r]){
r--;
continue;
}
if(nums[mid] < nums[r]){
r = mid;
}
else{
l = mid +1;
}
}
return nums[r];
}
}