欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

简单的二分查找

程序员文章站 2022-03-24 18:44:16
...

1.简介

    这里所讲解的简单的二分查找指的是在一个有序无重复元素的int类型的数组中查找需要的元素。

2.代码

    public int binarySearch(int[] a ,int value){
		int low = 0, hi = a.length - 1;
    	while(low <= hi){
    		int mid = low + ((hi - low)>>1);
    		if(a[mid] == value){
    			return mid;
    		}else if(a[mid] < value){
    			low = mid + 1;
    		}else if(a[mid] > value){
    			hi = mid - 1;
    		}
    	}
    	return -1;
    }

代码分析

举例:数组

int[] a = {2,3,5,7,8,10};
  1. low <= hi
    在进行二分查找的时候,当低位指针和高位指针相遇时,如果还没有找到要找的元素,这个时候就可以跳出循环了。

  2. low = mid + 1
    low不能mid(low=mid),假设low=mid,hi=mid - 1;当我们要找的元素 value >= max(数组中最大的元素),我们会找不到元素,也无法跳出循环 以举例数组为例,当我们要找 10 时,当 low = mid 这一步使 low = 4时;这时 low<=hi, int mid = low + ((hi - low)>>1) = 4, 这时mid的值没法再增加,low也会一直为4,虽然数组中有10,但是我们无法跳出循环,也无法找到10。

  3. hi = mid - 1
    hi不能为mid(hi=mid),假设 low = mid + 1 , hi = mid;当我们要找的元素 value < min(数组中最小的元素),数组中没有元素,但是无法跳出循环。以举例数组为例,当我们要找1时, 当 hi = mid 这一步使 hi = 0时;这时 low<=hi,int mid = low + ((hi - low)>>1) = 0, 这时 mid的值没法再减小, hi也会一直为0,虽然数组中没有1,但是无法跳出循环。

总结

    在对一个有序无重复的int数组进行二分查找的时候,就是不断的折半,直到高低位指针相遇跳出循环。还有要注意的就是当折半后low = mid + 1和hi = mid - 1 这些小细节。

相关标签: 算法