二分查找算法（递归与非递归两种方式）

淩亂°似流年 2024-04-17 23:45 15阅读 0赞

二分查找算法（递归与非递归两种方式）

**非递归方式**完成二分查找法。java代码如下所示。

public class BinarySearchUtil {
        /**
         * 二分查找普通实现。
         * @param srcArray 有序数组
         * @param key 查找元素
         * @return  不存在返回-1
         */
        public static int binSearch(int srcArray[], int key) {
            int mid;
            int start = 0;
            int end = srcArray.length - 1;
            while (start <= end) {
                mid = (end - start) / 2 + start;
                if (key < srcArray[mid]) {
                    end = mid - 1;
                } else if (key > srcArray[mid]) {
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
     public static void main(String[] args) {
        int srcArray[] = {3,13,23,33,43,53,63,73,83,93,103,203,303,403,1003};
         System.out.println(binSearch(srcArray,81));
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24
 *  25
 *  26
 *  27
 *  28
 *  29
 *  30

**采用递归方式**完成二分查找算法。代码如下所示。

public class BinarySearchUtil {

/\*\*  
\* 二分查找递归实现。  
\* @param srcArray 有序数组  
\* @param key 查找元素  
\* @return 不存在返回-1  
\*/  
public static int binarySearch(int\[\] shuzu, int numKey, int start, int end) \{  
int mid = (end - start) / 2 + start;  
if (start > end) \{  
return -1;  
\}  
if (numKey < shuzu\[mid\]) \{  
return binarySearch(shuzu, numKey, start, mid - 1);  
\} else if (numKey > shuzu\[mid\]) \{  
return binarySearch(shuzu, numKey, mid + 1, end);  
\} else \{  
return mid;  
\}  
\}

public static void main(String[] args) {
       int srcArray[] = {3,13,23,33,43,53,63,73,83,93,103,203,303,403,1003};
        System.out.println(binarySearch(srcArray, 10, 0, srcArray.length - 1));
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24
 *  25
 *  26
 *  27
 *  28
 *  29

</div>
                <link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-e44c3c0e64.css" rel="stylesheet">
                    </div>