| 2024-04-05 |

# 二分查找

前言：这道题真的可是说我做了很多遍就仿佛如英语的 abandon 仿佛如恶魔的低语一般伴随着我不会算法的日子。

# 题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target ，如果目标值存在返回下标，否则返回 -1 。

示例 1:
1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：

你可以假设 nums 中的所有元素是不重复的。

n 将在 [1, 10000] 之间。

nums 的每个元素都将在 [-9999, 9999] 之间

二分又叫分治法主要要点在于分而治之

关键在于分治时候的区间范围取值

版本一左闭右闭版本

public class Solution {
    public int Search(int[] nums, int target) 
    {
        //定义区间范围为 [left,right] 
        int right = nums.Length -1; 
        int left = 0;   
        while(left <= right){ //因为是闭合区间 才能取到等号
            //这里做减法 防止溢出
            int middle = left + (-left + right) /2; 
            //目标一定在左边 
            if(nums[middle] > target) 
            { //范围变成左闭右闭 [left,middle-1]
                right = middle -1;
            //目标在右边
            }else if(nums[middle] < target){
                //范围变成 [middle+1,right]
                left = middle + 1;
            }else{
                return middle;
            }
        }

        return -1;
    }
}

版本二左闭右开

public class Solution {
    public int Search(int[] nums, int target) 
    {
        //定义区间范围为 [left,right)
        int right = nums.Length; 
        int left = 0;   
        while(left < right){ //因为不是闭合区间 不取等号了
            //这里做减法 防止溢出
            //高级写法 >> 运算符是右移位运算符 它将 right - left 的结果右移一位，相当于将其除以2 逆天写法 平常感觉用不太到 学不太来
             int middle = left + ((right - left) >> 1);
            //目标一定在左边 
            if(nums[middle] > target) 
            { //不是上版的 middle-1了 范围变成左闭右闭 [left,middle)
                right = middle;  
            //目标在右边
            }else if(nums[middle] < target){
                //范围变成 [middle+1,right)
                left = middle + 1;
            }else{
                return middle;
            }
        }
        //无目标值
        return -1;
    }
}

# 运用分析

二分查找我认为是学习循环中判断与开闭区间关系的一道好题目

实际项目中没有用到过

叭叭两句 >> 这个玩意 GPT 告送我大多数情况替换 /2 是安全的但真的会有人这样用吗这样可读性就下降了可能性能有微小的提升吧注意的是右移运算不会出现小数

int c = -5;

// 使用右移位运算符
int result1 = c >> 1;  // 结果为 -3

// 使用除法
int result2 = c / 2;   // 结果为 -2

Console.WriteLine("结果1: " + result1);  // 输出-3
Console.WriteLine("结果2: " + result2);  // 输出-2

运行一下不一样感觉有点危险能少用还是少用吧

image-20240405014738787

我写好多次每次写二分还是废所白了就是记不住写这篇文章就是要逼我强行记住

tags: #算法