数据结构与算法-二分查找

Love The Way You Lie 2022-05-29 10:00 223阅读 0赞

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。  
二分查找的基本思想是将n个元素分成大致相等的两部分，取a\[n/2\]与x做比较，如果x=a\[n/2\],则找到x,算法中止；如果x < a\[n/2\],则只要在数组a的左半部分继续搜索x,如果x > a\[n/2\],则只要在数组a的右半部搜索x.  
时间复杂度可以表示O(h)=O(log2n)

基于循环的代码：

int BinarySearch_Recurrence(int sort_array[], int n, int target){
        int begin = 0;
        int end = n - 1;
        while (begin <= end){
            int mid = (begin + end) / 2;
            if (target == sort_array[mid])
                return 1;
            else if(target < sort_array[mid]){
                end = mid - 1;
            }
            else if(target > sort_array[mid]){
                begin = mid + 1;
            }
        }
        return 0;
    }

基于递归的代码：

int BinarySearch_Recursive(int sort_array[], int begin, int end, int target){
        if (begin > end){
            return 0;
        }
        int mid = (begin + end) / 2;
        if (target == sort_array[mid]){
            return 1;
        }
        else if (target < sort_array[mid]){
            return BinarySearch_Recursive(sort_array, begin, mid - 1, target);
        }
        else if (target > sort_array[mid]){
            return BinarySearch_Recursive(sort_array, mid + 1, end, target);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，223人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构——二分查找算法

1、算法描述二分查找算法：需求：在有序数组A内，查找值target，如果找到则返回目标值的索引号，否则返回-1 <table style="width:500px;"

ゞ浴缸里的玫瑰/ 2024年03月24日 16:12/ 0 赞/ 70 阅读

相关【数据结构与算法】二分查找

一、什么是二分查找？二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。二、

客官°小女子只卖身不卖艺/ 2022年11月28日 13:33/ 0 赞/ 140 阅读

相关数据结构与算法--二分查找算法

二分查找是折半查找，根据中间值一分为二。如果目标值大于中间值，那么就舍弃左边的从中间值的右边查找。如果目标值小于中间值，那么就舍弃右边的从中间值开始左边查找。注意：二分查

Dear 丶/ 2022年10月06日 02:56/ 0 赞/ 275 阅读

相关【数据结构与算法】九二分查找

【数据结构与算法】九二分查找适用于排好序的数据,如: int array[] = { 1,2,3,6,7,8,9}; 原理二分查找又

朴灿烈づ我的快乐病毒、/ 2022年08月21日 03:16/ 0 赞/ 189 阅读

相关【数据结构与算法】二分查找

基本思想首先将给定的值K与表中中间位置元素比较，若相等，则查找成功；若不等，则所需查找的元素只能在中间数据以外的前半部分或者后半部分，缩小范围后继续进行同样的查找，如

短命女/ 2022年08月11日 00:55/ 0 赞/ 209 阅读

相关数据结构与算法-二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。二分查找的基本

Love The Way You Lie/ 2022年05月29日 10:00/ 0 赞/ 224 阅读

相关数据结构与算法简述二分查找法

二分法查找：二分查找又称折半查找，每次查找，将数据分为两个部分，逐渐缩小查找范围，直到查到数据。时间复杂度为log2n。使用二分查找要求：一是必须是顺序存储数据结构，二

旧城等待，/ 2022年03月31日 04:20/ 0 赞/ 237 阅读

相关二分查找-查找算法-数据结构与算法

介绍二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

迷南。/ 2022年02月12日 12:23/ 0 赞/ 329 阅读

相关 JS数据结构与算法——二分查找

/ 二分查找 @param {Array} arr 待查找数组,数组需要已按照从小到大排序 @param {Any} x 待查找项 @return {Numbe

心已赠人/ 2022年02月02日 02:51/ 0 赞/ 277 阅读

相关二分查找（数据结构与算法）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

谁借莪１个温暖的怀抱￠/ 2021年12月23日 23:49/ 0 赞/ 308 阅读