0701算法实战

Java测试开发班
1

PPT

内容

leetcode 题目

刷题注意细节：

image
image1266×1100 85.8 KB

顺序查找

二分查找

  • 测试用例
package com.ceshiren.search;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class SearchTest {

    @Test
    void seqSearch() {
        Search search = new Search();
        // 如果找到则返回对应的下标。
        int [] list = {1,2,3,4,5,6};

        assertEquals(5, search.seqSearch(list, 6));
        assertEquals(0, search.seqSearch(list, 1));
        assertEquals(-1, search.seqSearch(list, 7));
    }
    @Test
    void demo(){
        int i = 12;
        // 获取数字位数的长度
        System.out.println(String.valueOf(i).length());

    }

    @Test
    void binarySearch() {
        Search search = new Search();
        // 如果找到则返回对应的下标。
        // 非常重要：！！二分必须为有序数组
        //
        int [] list = {1,2,3,4,5,6,7};

        assertEquals(5, search.binarySearch(list, 6));
        assertEquals(0, search.binarySearch(list, 1));
        assertEquals(-1, search.binarySearch(list, 9));
    }

    }

相关源码

课堂练习

  • 答案在ppt里面：
  • 二分查找
  • 冒泡排序
  • 递归：
    1. 编写一个递归函数来计算列表包含的元素数。
    2. 通过递归找到列表中最大的数字。
    3. 通过递归的方式实现二分查找算法。
  • 快速排序
2 
public int binarySearch(int[] list, int i) {
        int low = 0;
        int high = list.length -1;

        while (low<=high) {
            int mid = (low + high) / 2;
            if (list[mid] == i) {
                return mid;
            } else if (list[mid] < i) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }