【Java】和【C语言】实现一个有序数组的二分查找

红太狼 2023-10-05 23:14 46阅读 0赞

**目录**

1.二分查找介绍

2. 二分查找代码实现

2.1 Java代码实现

2.2 C语言代码实现

3. 查找的思路

3.1 mid小于要找的元素

3.2 mid大于要找的元素

4. 二分查找优缺点

--------------------

## 1.二分查找介绍 ##

*二分查找也叫折半查找，首先计算数组中间的位置（元素个数除以2），将数组中间位置处的下标与查找的元素进行比较，如果相等，则查找成功；否则利用中间位置将数组分为左、右两个部分，如果中间位置的下标大于查找的元素，则查找左子表，否则查找右子表。重复上面的过程，直到找到要查找的关元素为止，否则查找失败不存在此元素。*

## 2. 二分查找代码实现 ##

### 2.1 Java代码实现 ###

/**
     * @project 二分查找
     **/
    public static int binarysearch(int[] array, int k) {
        int sz = array.length;//求数组长度
        int left = array[0];//左下标
        int right = sz - 1;//右下标
        while (left <= right) {
              int mid = (left + right) / 2;//中间下标
              if (array[mid] > k) {//要找的元素在左边
                 right--;
              } else if (array[mid] < k) {//要找的元素在右边
                  left++;
              } else {//找到了返回下标
                  return mid - 1;//下标是从0开始的，每一个元素的下标都是 n-1
              }
        }
            return -1;
    }
    
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        //int k = 7;//查找的元素
        Scanner input = new Scanner(System.in);
        System.out.print("输入要查找的元素：");
        int k = input.nextInt();//输入要查找的元素
        int ret = binarysearch(array, k);
        /**
         * @rule 返回1说明找到了 - 返回-1说明没找到
         * @rule 输出找到元素的下标
         **/
        if (-1 == ret) {
           //找不到
           System.out.println("找不到，因为元素不存在");
        } else {
            System.out.println("找到了，下标是：" + array[ret]);
        }
    }

![a719e23dcddb4dfc94c2c5405fb1f882.png][]

### 2.2 C语言代码实现 ###

#include<stdio.h>
    
    int binary_search(int arr[], int k, int sz)
    {
        int left = 0;//左下标
        int right = sz - 1;//右下标
        while (left <= right)//左下标<=右下标说明中间还有元素要查找
        {   //中间元素的下标
            int mid = (left + right) / 2;//mid就是折半之后的数组元素个数
            //mid-1和mid+1逐渐接近要找的元素
            if (arr[mid] > k)//mid数组的下标大于k说明要找的元素在数组的左边
            {
                right = mid - 1;//mid-1赋给右边的左边
            }
            else if (arr[mid] < k)//mid数组的下标小于k说明要找的元素在数组的右边
            {
                left = mid + 1;//mid+1赋给左边的下标
            }
            else
            {
                return mid;//返回找到的下标
            }
        }
        return -1;//整个数组都查找了一遍，没有要找到要找的元素就返回-1
    }
    int main()
    {
        int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
        int k = 7;//要找的元素，找到后输出它的下标
        //数组的个数=数组的总大小/数组一个元素的大小
        int sz = sizeof(arr) / sizeof(arr[0]);//sz就是数组元素的个数
        int ret = binary_search(arr, k, sz);
        if (-1 == ret)//ret等于接收的-1说明整个数组没有要找的元素
        {
            printf("找不到了\n");
        }
        //ret不等于接收的-1就说明找到了
        else
        {
            printf("找到了，下标是:%d\n", ret);//输出找到的元素下标
        }
        return 0;
    }

![6101ecc465544506bd34850888e3b56e.png][]

## **3. 查找的思路** ##

### **3.1 mid小于要找的元素** ###

![41d7aeb8c8fe449b9e6635e363109c09.png][]

### **3.2 mid大于要找的元素**  ###

![02d5a9349f9445858c300afd9fd5a933.png][]

## 4. 二分查找优缺点 ##

1.  优点是比较次数少，查找速度快，平均性能好；
2.  其缺点是要求待查表为有序表，且插入删除困难。
3.  因此二分查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：查找序列是顺序结构，有序。

[a719e23dcddb4dfc94c2c5405fb1f882.png]: https://img-blog.csdnimg.cn/a719e23dcddb4dfc94c2c5405fb1f882.png
[6101ecc465544506bd34850888e3b56e.png]: https://img-blog.csdnimg.cn/6101ecc465544506bd34850888e3b56e.png
[41d7aeb8c8fe449b9e6635e363109c09.png]: https://img-blog.csdnimg.cn/41d7aeb8c8fe449b9e6635e363109c09.png
[02d5a9349f9445858c300afd9fd5a933.png]: https://img-blog.csdnimg.cn/02d5a9349f9445858c300afd9fd5a933.png