查找算法

Posted on Edited on In Waline:

本文使用java语法实现了对查找算法的表述,采用递归和非递归两种方式.

####0x01.二分查找法

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class binarySearchRecursive 
{
    public static int binarySearchRecursive(int[] arr, int start, int end, int hkey) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end - start)/2;
        if(arr[mid] > hkey){
            return binarySearchRecursive(arr, start, mid-1,hkey);
        }
        if (arr[mid] < hkey){
            return binarySearchRecursive(arr, mid+1, end,hkey);
        }
        return mid;
    }

    public static void main(String[] args){
        int[] arr = {1,2,4,6,7};
        int result = binarySearchRecursive(arr,0,arr.length-1,4);
        System.out.println("result = " + result);
    }
}

#####非递归

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
import java.util.*;

public class binarySearchNoneRecursive
{
    public static void main(String[] args){
        int[] arr = {1,3,5,6,7};
        int result = binarySearch(arr, 0, arr.length, 7);
        System.out.println("result = " + result);
    }

    public static int binarySearch(int[] arr, int start, int end, int hkey){
        int result = -1;

        while (start <= end){
            int mid = start + (end - start)/2;
            if (arr[mid] > hkey){
                end = mid - 1;
            } else if (arr[mid] < hkey) {
                start = mid + 1;
            } else {
                result = mid;
                break;
            }
        }
        return result;
    }
}