Java和Python实现二分搜索算法

末蓝、 2023-06-15 13:29 35阅读 0赞

二分搜索算法需要传入两个数据，一个是排好序的数组，一个是要找的数！算法会找出来要找的数在数组哪里，下标在哪里，并输出！

//二分搜索
    public class TwoPointSearch {
    	
    	public int TwoPoint(int problem[],int x) {
    		//数组下边从0开始，长度是比下标大1的，所以要减一
    		int left = 0,right = problem.length-1;
    		//取中间的元素进行判断
    		int center = (left+right)/2;
    		if(problem[problem.length-1]<x) { //要找的数比最后一个数大说明不在里面
    			return -1;
    		}else if(problem[0]>x) { //要找的数比第一个数小说明不在里面
    			return -1;
    		}else {
    			while (left <= right) {
    				if(problem[center]==x) { //中间数等于要找的数
    					return center;
    				}else if(problem[center]>x) { //中间数大于要找的数
    					right = center-1;
    				}else if(problem[center]<x) { //中间数小于要找的数
    					left = center+1;
    				}
    				center = (left+right)/2; //搜索完后再次把要选择的范围减小一半
    			}
    		}
    		return 000;	//方法需要返回值
    	}
    	
    	public static void main(String[] args) {
    		TwoPointSearch TPS = new TwoPointSearch();
    		int[] problems = new int[100];
    		int i = 0,find=66;
    		while (i < 100) {	//向数组中添加数据
    			problems[i] = i+1;
    			i += 1;
    		}
    		int index = TPS.TwoPoint(problems,find);
    		if(index==-1) {
    			System.err.println("要找的数"+find+"不在该数组里面！");
    		}else {
    			System.out.println("要找的数"+find+"在该数组下标为"+index+"的位置！");
    		}
    		
    	}
    }

输出结果为：

![20191122175546446.png][]

下面是用Python代码实现

class TPS:
        @staticmethod
        def TwoPointSearch(problem,x):
            left=0      # 列表最开始下标为0
            right=len(problem)-1    #列表下标最大值是列表长度-1
            center = int((left+right)/2)    #取中间值
            if problem[-1]<x:   #如果列表最后一个元素小于要找的数  说明该数不在列表里面
                print("要找的数"+str(x)+"不在该列表里面！")
            elif problem[0]>x:   #如果列表第一个元素大于要找的数  说明该数也不再列表里面
                print("要找的数"+str(x)+"不在该列表里面！")
            else:
                while left<=right:
                    if problem[center]==x:      #相等则返回要找的数的下标
                        print("要找的数"+str(x)+"在该数组下标为"+str(center)+"的位置！")
                        break
                    elif problem[center]>x:     #中间数大于要找的数  说明数在左边
                        right = center-1
                    elif problem[center]<x:     #中间数小于要找的数  说明数在右边
                        left=center+1
                    center=int((left+right)/2)    #每执行一次  去掉一半
    
    
    problem=range(1,100)
    find=101
    TPS.TwoPointSearch(problem,find)

运行结果

![20191122213146200.png][]

有不明白的尽管留言！共同进步！

[20191122175546446.png]: https://img-blog.csdnimg.cn/20191122175546446.png
[20191122213146200.png]: https://img-blog.csdnimg.cn/20191122213146200.png