二分搜索
2022-04-25 23:02:01

二分搜索
數(shù)組必須是排序好的
java 實現(xiàn)

public class App {
    public static void main(String[] args) throws Exception {
        // 目標數(shù)組
        int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        // 目標元素
        int dstNum = 10;
        // 左索引
        int leftIndex = 0;
        // 右索引
        int rightIndex = arr1.length - 1;
        // 中間索引
        int midIndex = (leftIndex + rightIndex) / 2;

        // 目標位置
        int dstIndex = -1;
        while (leftIndex <= rightIndex) {
            // 如果命中
            if (arr1[midIndex] == dstNum) {
                dstIndex = midIndex;
                break;
            }

            if (arr1[midIndex] > dstNum) {
                // 如果中間數(shù)大于目標數(shù)，右索引左移到中間位置-1
                rightIndex = midIndex - 1;
            } else {
                // 中間數(shù)大于目標數(shù)， 左索引右移到中間位置 +1
                leftIndex = midIndex + 1;
            }

            // 重新計算midIndex
            midIndex = (leftIndex + rightIndex) / 2;

        }
        System.out.println("結(jié)果:" + dstIndex);

    }
}

python 實現(xiàn)

# coding: utf-8
if __name__ == '__main__':
    arr = [1,2,3,4,5,6,7,8,9]
    left_index = 0
    right_index = len(arr)-1
    dst_num = 6
    dst_index = -1
    mid_index = int((left_index + right_index) / 2)
    while left_index <= right_index:
        if arr[mid_index] == dst_num:
            dst_index = mid_index
            break

        if arr[mid_index] < dst_num:
            left_index = mid_index + 1
        else:
            right_index = mid_index - 1
        
        mid_index = int((left_index + right_index) / 2)
    
    print(f"結(jié)果:{mid_index}")

優(yōu)化
防止整數(shù)相加溢出
計算中位數(shù)使用

int midIndex = leftIndex + ((rightIndex - leftIndex) >> 1)

python

mid_index = left_index + ((right_index - left_index) >> 1)