二分搜索(标准示例)

系统管理员 2022-08-30 01:45 158阅读 0赞

二分搜索适合在一个**有序**的序列中**搜索某值**。

二分搜索也称为二分查找或折半查找，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。它的基本思想：将n个元素分成数量大致相同的两部分，取a\[n/2\]与想要查找的x进行比较，如果x==a\[n/2\]则找到x，算法终止，如果x<a\[n/2\]则我们只要在数组a的左半部分继续搜索x(这里假设数组元素呈升序排列)，如果x>a\[n/2\]，则我们只要在数组a的右半部分继续搜索x。

二分搜索的标准框架如下：  
递归方式：

若待搜索空间为空，返回-1
    否则
    	mid = (low + high) / 2;
    	若x等于a[mid],搜索成功，返回mid;
    	若x小于a[mid],则在左半区间搜索;
    	若x大于a[mid]，则在右半区间搜索;

代码如下：

int search(int a[], int left, int right, int target)
    { 
         if(left > right)
              return -1;
         else{ 
              int mid = left + (right - left)/2;  //避免left+right溢出
              if(target == a[mid])
                   return mid;
              if(target < a[mid])
                   return search(a, left, mid-1, target);
              else
                   return search(a, mid+1, right, target);
         }
    
    }

循环方式：  
不在赘述了，直接上代码：

int searchInsert(int* nums, int numsSize, int target){ 
        
        int left = 0;
        int right = numsSize -1;
        
        while(left <= right)
        { 
            int mid = left + (right - left)/2;
            if(nums[mid] < target)
            { 
                left = mid + 1;
            }
            else
            { 
                right = mid - 1;
            }
    
        }
        return left;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关二分搜索技术

例如，给定n个元素序列，这些元素是有序的（假定为升序），从序列中查找元素x。用一维数组S\[\]存储该有序序列，设变量low和high表示查找范围的下界和上界，middle

深藏阁楼爱情的钟/ 2022年11月15日 14:17/ 0 赞/ 183 阅读

相关二分搜索模板

ll binary_search(ll key, ll a[], ll n) { ll low = 1; ll high = n; ll mi

柔情只为你懂/ 2022年11月08日 11:28/ 0 赞/ 222 阅读

相关 1010 二分搜索

Description 给定一递增有序数组a[0,1,...,n-1], 请在数组中搜索给定元素. 搜索过程中请使用mid=(low+high)/2. Input

Myth丶恋晨/ 2022年09月11日 12:25/ 0 赞/ 271 阅读

相关二分搜索(标准示例)

二分搜索适合在一个有序的序列中搜索某值。二分搜索也称为二分查找或折半查找，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。它的基本

系统管理员/ 2022年08月30日 01:45/ 0 赞/ 159 阅读

相关二分搜索法

二分搜索法(C++) // //Description:二分搜索法 // include <iostream> using names

朱雀/ 2022年06月18日 01:55/ 0 赞/ 280 阅读

相关二分搜索算法

二分搜索算法是计算机程序设计中的基础算法，1946年第一篇二分搜索算法的论文发表，第一个正确的算法实现是在1962年，中间相隔16年，这一事实令人深思。据了解训练有素的程序员仅

古城微笑少年丶/ 2022年06月17日 22:48/ 0 赞/ 214 阅读

相关二分搜索

//二分查找的前提：有序序列 public static int binSearch(int[] arr,int number){

约定不等于承诺〃/ 2022年06月12日 13:38/ 0 赞/ 196 阅读

相关 1152: 二分搜索

Description 在有序序列中查找某一元素x。 Input 首先输入一个正整数n(n<=100000)，表示该序列有n个整数，然后按从小到大的顺序输入n个整

清疚/ 2022年06月11日 03:13/ 0 赞/ 246 阅读

相关二分搜索

给定已经排好序的N个元素a\[0,m-1\],找到特定元素x 因为是拍好的序的N个元素，所以可以通过比较的方法不停的判断其属于哪个区间，通过二分每次只需在1/2区间里选择

矫情吗；*/ 2022年05月28日 03:29/ 0 赞/ 182 阅读

相关二分搜索查找

一、对数　　![1007094-20190114154412410-1669210589.png][] 二、代码　　 1 def binary_se

缺乏、安全感/ 2021年12月09日 00:57/ 0 赞/ 283 阅读