牛客网刷题笔记_顺序表查找

牛客网刷题笔记：

查找-day01

1、顺序表查找概念

正确解析：

顺序查找指从第一个数据元素开始查找到最后

而顺序表查找是顺序存储结构上进行查找

2、折半查找具体题目

正确解析：

选D。

索引从0到12，left=0，right=12。

1、mid=(left+right)/2=6，与70比较，70<75，left=mid+1=7，right=12

2、mid=(left+right)/2=9.5，向下取整索引为9，则与81比较，81>75，因此right=mid-1=8，left=7

3、mid=(left+right)/2=7.5，向下取整索引为7，与73比较，73<75，left=mid+1=8，right=8

4、mid=(left+right)/2=8，与75比较，75=75，返回。

仔细写了一下二分查找法（即折半查找法）

package com.find;
/*
@author Zhou
@date   2020/2/27-17:46
*/

public class BinarySearch {
    public static void main(String[] args) {
        int []arr = {10,13,22,34,41,52,63,79,85,96,107};
        System.out.println(binarySearch(arr,63));
    }

    private static int binarySearch(int[]array,int key){
        int middle;
        int left = 0;
        int right = array.length;
        middle = (left + right) / 2;
        for (int i = 0;i < array.length ; i++){
            if (array[middle] > key){
                right = middle - 1;
                middle = (left + right) / 2;
            }else if (array[middle] < key){
                left = middle + 1;
                middle = (left + right) / 2;
            }else {
                break;
            }
        }
        return middle;
    }
}

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
28
29
30
31
32

输出结果如下：

3、关于折半查找的代码解析

正确解析：

需要对折半查找代码更加熟练理解

4、斐波那契查找和折半查找性能比较

正确解析: