查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
列表查找：线性表查找，从列表中查找指定的元素

输入：列表，待查找的元素 输出：元素下标，未找到元素的时一般返回None或-1

内置列表查找函数：index()

顺序查找

也叫线性查找，从列表的第一个元素开始，顺序进行搜索，直到找到元素或者搜索到列表的最后一个元素为止。
image.png
时间复杂度：O(n)

二分查找

又叫折半查找，从有序列表的初始候选区li【0:n】开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
从列表中查找元素3：
image.png
image.png
image.png
image.png
从候选区这个概念，这个问题会比较简单,折半使候选区缩小。复杂度O(logN)

  1. package com.algorithm.demo;
  3. /**
  4.  * @Author leijs
  5.  * @date 2022/4/9
  6.  */
  7. public class Search {
  8.     public static void main(String[] args) {
  9.         int[] array = new int[] {1,2,3,4,5,6,7,8,9};
  10.         System.out.println(binarySearch(array, 3));
  11.     }
  13.     public static int binarySearch(int[] list, int value) {
  14.         int left = 0, right = list.length -1;
  15.         while (left <= right) {
  16.             int midIndex = (left + right) / 2;
  17.             int midValue = list[midIndex];
  18.             if (midValue == value) {
  19.                 return midIndex;
  20.             } else if (midValue < value) {
  21.                 // 说明在右侧
  22.                 left = midIndex + 1;
  23.             } else {
  24.                 right = midIndex - 1;
  25.             }
  26.         }
  27.         return -1;
  28.     }
  30. }
  • 注意index() 实现的是顺序查找
  • 二分查找要求有序，非有序要先排序，所以这其中就要考虑顺序问题。