二分查找法的实现及原理

拼搏现实的明天。 2022-11-19 09:45 233阅读 0赞

# 二分搜索法 #

**原理：折半查找，直到查找到的元素与目标元素相等，查找终止**

## 二分搜索法的实现 ##

剖析：

**注：**

*  **1.基于排序的代码才能使用该方法**
 *  **2.查找的终止条件：——> 中间的那个元素恰巧 等于 要查找的元素**

假定现有一个数组arr = \[20,21,22,23,24,25,26,27,28,29\]; 使用二分搜索法查找该数组中的某一个元素

*  **实现原理如下：**
 *  （起始元素的下标 + 终止元素的下标）/ 2 --> 中间元素的下标
 *  判断位于该中间的元素是否小于要查找的元素，如果小于，则 **起始元素的下标应该更新为**—— 中间元素的下标 + 1
 *  判断位于该中间的元素是否大于要查找的元素，如果大于，则 **终止元素的下标应该更新为** ——中间元素的下标 - 1  
      
      
    需求：  
    从该数组中查找 28 ，如果有该元素，返回该元素的下标值,如果没有该元素，返回-1
 *  查找过程：
 *  起始元素下标为0 终止元素下标为arr.length-1  
      
    
 *  第一次查找：
 *  （0 + 9）/ 2 ——> 4
 *  arr\[4\] = 24
 *  24 < 28 , 中间元素的下标更新为 4+1=5  
      
    
 *  第二次查找：
 *  (5 + 9)/2 ——> 7
 *  arr\[7\] = 27
 *  27 < 28, 中间元素的下标更新为 7+1=8  
      
    
 *  第三次查找
 *  (8+9)/2 —— > 8
 *  arr\[8\] = 28
 *  28 = 28 找到元素，循环终止  
    返回对应下标

**代码实现如下**

package Sort;
    public class dichotomizingSearch { 
    	public static void main(String[] args) { 
    		int[] arr = { 20,21,22,23,24,25,26,27,28,29};
    		int result = dichotomizeSearch(arr,28);
    		System.out.println(result);
    	}
    
    	private static int dichotomizeSearch(int[] array,int ele) { 
    		int begin = 0;
    		int end = array.length-1;
    		
    		while (begin <= end) { 
    			int mid = (begin+end)/2;
    			if (array[mid] == ele) { 
    // 如果找到的中间元素与要查找的元素相等，则直接返回中间元素的下标
    				return mid;
    			}else if(array[mid] < ele) { 
    // 找到的中间元素 < 要查找的元素 此时目标元素需要向右搜索，起始的下标需要更新
    				begin = mid +1;
    			}else { 
    // 找到的中间元素 > 要查找的元素 此时目标元素需要向左搜索,终止的下标需要更新
    				end = mid -1;
    			}
    		}
    		return -1;
    	}
    }