二分查找逻辑

rain-xuan

<h2>二分查找</h2>

==逻辑==：

==思路==：

1. 双指针，一个指向数组首地址，一个指向数组尾
2. 循环,条件是如果右边永远大于左边的值
3. 计算中间值
4. 判断中间值与目标值的大小
5. 如果中间值小于目标值，就把中间值赋给left
6. 如果中间值大于目标值，就把中间值赋给right
7. 循环执行，找到返回目标值的下标加一，找不到，返回负一

<h3>代码实现</h3>

#include <stdio.h>
#include <stdlib.h>

//search函数的实现
int search(int arr[], int arrsize, int target)
{
    //1.双指针，一个指向数组首地址，一个指向数组尾
    int left = 0;
    int right = arrsize - 1;
    int middle = 0;
    //2.循环,条件是如果右边永远大于左边的值
    while (right >= left)
    {
        //3.计算中间值
        middle = (right + left) / 2;
        //4.判断中间值与目标值的大小
        //4.1 如何相等直接返回
        if (arr[middle] == target)
            return middle + 1;
        //4.2 如果中间值大于目标值
        if (arr[middle] > target)
            right = middle;
        //4.3 如果中间值小于目标值
        else
            left = middle;
    }
    //查找失败
    return -1;
}
int main()
{
    //准备排序好的数组，从大到小，从小到大都可以，此处用的是从小到大
    int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
    //打印返回值 -1--->没找到，否则返回下标加一
    printf("%d\n", search(arr, sizeof(arr) / sizeof(int), 8));
    system("pause");
    return 0;
}

<h3>运行截图</h3>

rain-xuan

zxxzb 发表于 2021-3-15 20:15
多个数组中呢？怎么查找

这个可能要其它的算法思想结合了，像啥子分而治之，但是二分的主思想应该不变，一个按一定规律排序好的序列，然后采用这种算法吧。我也还在路上，以上是我的观点，不知道对不对。

yacc

楼主加油，不过markdown里面写h2标签是什么鬼

QingYi.

middle = (right + left) / 2;
改为 （l + r )>>1
细节

QingYi.

[Java] 纯文本查看 复制代码

while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;

0Ling0

针对不同问题leetcode给出三种方式

沧浪风澜

最近正好在学习数据结构与算法，学习了

rain-xuan

QingYi. 发表于 2021-3-15 17:29
[mw_shl_code=java,true]while (l < r)
    {
        int mid = l + r >> 1;

谢谢，以后注意细节

rain-xuan

yacc 发表于 2021-3-15 17:19
楼主加油，不过markdown里面写h2标签是什么鬼

，学习点html的知识，想着多用用，于是就混编了，为了美观，以后注意。

zxxzb

多个数组中呢？怎么查找