二分查找的两种实现（Java）

比眉伴天荒 2022-04-17 04:52 113阅读 0赞

**查找过程**  
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。  
**算法要求**  
1.必须采用顺序存储结构。  
2.必须按关键字大小有序排列。  
**时间复杂度**  
比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。  
由于n/2k取整后>=1，即令n/2k=1，  
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)。  
**代码实现**

package find;
    
    public class BinarySearch {
    
    	// 循环实现
    	public static int binarySearch(int[] data, int target) {
    		int low = 0;
    		int high = data.length;
    		while (low <= high) {
    			int mid = (low + high) / 2;
    			if (target == data[mid]) {
    				return mid;
    			} else if (target < data[mid]) {
    				high = mid - 1;
    			} else {
    				low = mid + 1;
    			}
    		}
    		return -1;
    	}
    
    	// 递归实现
    	public static int binarySearch(int[] data, int target, int beginIndex, int endIndex) {
    		if (target < data[beginIndex] || target > data[endIndex] || beginIndex > endIndex) {
    			return -1;
    		}
    		int midIndex = (beginIndex + endIndex) / 2;
    		if (target > data[midIndex]) {
    			binarySearch(data, target, midIndex + 1, endIndex);
    		} else if (target < data[midIndex]) {
    			binarySearch(data, target, beginIndex, endIndex - 1);
    		} else {
    			return midIndex;
    		}
    		return -1;
    
    	}
    
    	public static void main(String[] args) {
    		int[] data = { 1, 5, 8, 9, 16, 25, 47, 89, 95, 101 };
    		int target = 16;
    		System.out.println(binarySearch(data, target));
    		System.out.println(binarySearch(data, target, 0, data.length - 1));
    	}
    
    }

循环实现，返回索引位置:4
    递归实现，返回索引位置:4