大飞

大飞 关注TA

挑战一切!

大飞

大飞

关注TA

挑战一切!

  •  世界的顶端
  • 混口饭吃
  • 写了333,609字

最近回复

该文章投稿至Nemo社区   Python  板块 复制链接


Python 二分查找算法

发布于 2018/09/21 00:48 1,493浏览 0回复 2,558

"""
 递归二分查找算法 将排序好的数组(比如从小到大)或队列一分二为,选取中间值比较
 如果要查找的数值比中间值大,说明要查找的数值在前半部分,相反在后半部分,继续将
 前半部分(或后半部分)一分为二,如此循环,直到找出中间值为索要寻找的数值
"""
numberArray = [1, 3, 5, 7, 9, 11, 13]


def binary_search(array, search_data, start_index, end_index):
    # python 整数相除如果有小数点会返回浮点型,这个跟Java不同
    mid_index = int((start_index + end_index) / 2)
    # 如果查找的数据不存在返回-1
    if search_data < array[start_index] or search_data > array[end_index] or start_index > end_index:
        return -1
    # 查找的数据在后半部分
    if search_data > array[mid_index]:
        return binary_search(array, search_data, mid_index + 1, end_index)
    # 查找到数据在前半部分
    elif search_data < array[mid_index]:
        return binary_search(array, search_data, start_index, mid_index - 1)
    # 最终索引
    else:
        return mid_index


print(binary_search(numberArray, 3, 0, len(numberArray) - 1))
print(binary_search(numberArray, 11, 0, len(numberArray) - 1))
print(binary_search(numberArray, 7, 0, len(numberArray) - 1))
print(binary_search(numberArray, 4, 0, len(numberArray) - 1))
package com.hangzhou.servicezuul;

/**
 * 二分查找又称折半查找,它是一种效率较高的查找方法。
 *   【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
 */
public class BinarySearch {
   public static void main(String[] arg) {
      int[] numberArray = new int[]{1, 3, 5, 7, 9, 11, 13};
      System.out.println(binarySearch(numberArray, 3, 0, numberArray.length - 1));
      System.out.println(binarySearch(numberArray, 11, 0, numberArray.length - 1));
      System.out.println(binarySearch(numberArray, 7, 0, numberArray.length - 1));
      System.out.println(binarySearch(numberArray, 6, 0, numberArray.length - 1));


   }

   /**
    * 递归二分查找算法
    * @return 索引
    */
   public static int binarySearch(int[] array, int searchData, int startIndex, int endIndex) {
      int midIndex = (startIndex + endIndex) / 2;
      // 查找的数据不存在
      if (searchData < array[startIndex] || searchData > array[endIndex] || startIndex > endIndex) {
         return -1;
      }
      // 查找的数据在后半部分
      if (searchData > array[midIndex]) {
         return binarySearch(array, searchData, midIndex + 1, endIndex);
         // 查找的数据在前半部分
      } else if (searchData < array[midIndex]) {
         return binarySearch(array, searchData, startIndex, midIndex - 1);
      } else {
         return midIndex;
      }
   }
}

执行结果如下:

/Users/lyf/PycharmProjects/venv/bin/python /Users/lyf/PycharmProjects/TCPChatDemo/BinarySearch.py

1

5

3

-1

Process finished with exit code 0

点赞(0)
点了个评