【分治法】二分搜索技术java实现

刺骨的言语ヽ痛彻心扉 2023-03-13 11:40 12阅读 0赞

### 搜索问题 ###

问题描述：**给定已按升序排好序的n个元素a\[0:n-1\]，搜索一特定元素x**

要求：**对该问题设计有效的求解算法，并分析算法在最坏情况的时间复杂性。**

### 顺序查找 ###

举例1，设n=6，a=\[1,3,5,6,7,9\]，搜索问题  
当前情况下，进行搜索的话，对数组当中的元素可以依次扫描。  
**最好的情况**是数组当中第一个元素就是要搜索的元素x，只需要比较一次，**最坏的情况下**，从头扫到尾，这个时候在找到了元素x，或者元素x不存在，此时需要n次比较。复杂性0n)是线性级别的。

那么能不能进一步改进呢？我们发现在顺序查找中，没有利用n个元素排好序这一特性

### 搜索问题—分治法 ###

基本思想：将大的问题分割成规模比较小的问题，分而治之。  
对已经升序排好序的n个元素。下图所示，最容易想到的分割方法是一刀两断，此时将一个大问题，分解为两个子问题，处于均衡的考虑，每个子问题的规模为n/2 ,因此去数组中位数下标即可。元素即为a\_mid。  
分三种情况：  
第一种情况如果找到元素x，刚好等于a\_mid，搜索停止，已经找到。  
第二种情况如果x<a\_mid，这个时候说明搜索的元素x在第一个子问题当中，完全没有必要对第二个子问题进行搜索。  
第三种情况如果x>a\_mid，说明搜索的元素x在第二个子问题当中，完全没有必要对第一个子问题进行搜索。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]

### 总结 ###

基本思想：将n个元素分成大致相等的两部分。  
1、x=a\_mid算法终止。  
2、x<a\_mid在数组的左半部分继续搜索。  
3、x>a\_mid在数组的右半部分进行搜索。

### java代码 ###

/**
     * @Author Xiang
     * @Description 分治递归查找
     * @Date 2020.5.13
     */
    public class BinarySearch {
        
        public static void main(String[] args) {
        
            BinarySearch search = new BinarySearch();
            int[] arr={
        1,2,3,4,5,6,7,8,9,10};
            System.out.println(search.binarySearch(0, arr, 0, arr.length - 1));
        }
        public int binarySearch(int value,int[] arr,int left,int right){
        
            if (left>right){
        
                return -1;
            }
            int mid=(left+right)/2;
    
            if (arr[mid]==value){
        
                return mid;
            }else if (arr[mid]<value){
        
                return binarySearch(value,arr,mid+1,right);
            }else {
        
                return binarySearch(value,arr,left,mid-1);
            }
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]: /images/20230312/086968bd64fc42848ab2f80047ebd930.png