二分法查找的java和python实现

╰半夏微凉° 2022-05-12 15:20 152阅读 0赞

二分法的核心思想为

对于一个有序的数组，

1，如果目标值大于数组中间那个值，那么，其索引一定出现数组的后半部分；

2，如果目标值小于数组中间那个值，那么，其索引一定出现在数组的前半部分。

以此类推，直到找到那个值为止。

Java实现：

import java.util.Arrays;
    
    public class BinarySearch {
    
        public static int rank(int key,int[] a){
    
            int lo = 0;
            int hi = a.length - 1;
    
            while(lo <= hi) {
                int mid = lo + (hi-lo)/2;
                if (key < a[mid]) {
                    hi = mid -1;
                }else if( key > a[mid]){
                    lo = mid +1;
                }else{
                    return mid;
                }
            }
    
            return -1;
        }
    
        public static void main(String[] args) {
    
            int[] a={0,13,25,23,33,45,35,22};
    
            Arrays.sort(a);
    
            System.out.println(BinarySearch.rank(23,a));
    
    
    
        }
    }

Python实现

a = [0,13,25,23,33,45,35,22];
    print(a);
    #[0, 13, 25, 23, 33, 45, 35, 22]
    a.sort();
    print(a)；
    #[0, 13, 22, 23, 25, 33, 35, 45]
    def binarySearch(nums, target):
            start = 0
            end = len(nums) -1
            while start <= end:
                middle = (start + end) // 2
                if target > nums[middle]:
                    start = middle + 1
                elif target < nums[middle]:
                    end = middle - 1
                else:
                    return middle
            return -1
    print(binarySearch(a,13));
    # 1