苏木三少
错的不是你,而是这个世界。

<每天一个> 算法实现之二分查找

二分查找

一、算法介绍

(数学领域)二分法:

对于区间[a,b]上连续不断且f(a)·f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。

(计算机领域)二分法:

(1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。

(2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。

(3)如果某一步数组为空,则表示找不到目标元素。

时间复杂度

1.最坏情况查找最后一个元素(或者第一个元素)Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情况查找中间元素O(1)查找的元素即为中间元素(奇数长度数列的正中间,偶数长度数列的中间靠左的元素)

二、注意事项

二分法要求数组必须是有序的。
数组的长度是确定的。

三、代码实现。

我写的是输入一个数字组成的字符串,判断数字是否在数组中。(java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearch {
    public static int rank(int key,int[] a)
    {//数组必须是有序的。
        int lo = 0;
        int hi = a.length - 1;
        while(lo <= hi)
        {//被查找的键要么不存在,要么必然存在于a[l0..hi]中。
            int mid = lo + (hi - lo)/2;//求中间值a[mid]的下标mid
            if(key < a[mid])//key值小于中间值
            {
                hi = mid -1;//最高小标值变为下标mid-1
            }
            else if(key > a[mid])//key值大于中间值
            {
                lo = mid + 1;//最低下标值变为下标mid+1
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        int inputChar[]=new int[5];
        System.out.println("请输入一组有序的数组");
        for(int i=0;i<5;i++)
        {
            Scanner scan = new Scanner(System.in);
            inputChar[i] = scan.nextInt();
        }
        System.out.println("请输入要查找的key");
        Scanner input = new Scanner(System.in);
        int key = input.nextInt();
        int b = rank(key,inputChar);
        if(b<0)
        {
            System.out.println("元素key不在其中");
        }
        else
        {
            System.out.println("元素key在其中");
        }
    }
}

 

赞(5) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » <每天一个> 算法实现之二分查找

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约