-
顺序查找 :
-
优点 : 编码简单,容易理解,没啥逻辑,就挨个比较
-
数据靠前的话,效率也比较高
-
缺点 : 随机查询效率较低
-
二分法查找
-
1 建立在排序的基础上
-
2 用于查找固定有序的数据
-
实现原理 :
-
每次和中间的比较
-
1 确定起始下标和结束下标
-
2 确定中间下标,然后和目标数据开始比较
-
3 如果相等.就返回中间下标即可
-
4 如果目标数据大于中间数据 , 结束值不变,起始值=中间值+1, 重新生成中间值,继续比较
-
5 如果目标数据小于中间数据,起始值不变,结束值=中间值-1.重新生成中间值,继续比较
-
6 当起始值大于结束值的时候,说明不存在
二分法查找代码实现：
public class BinarySearch {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 6, 8, 13, 22, 14, 16, 26, 84, 35, 133 };
// 排序
Arrays.sort(arr);
arr = new int[9999999];
for (int i = 0; i < arr.length; i++) {
arr[i] = i+1;
}
int target = 1;
int result = search(arr, target);
System.out.println(result);
result = binarySearch(arr, target);
System.out.println(result);
}
public static int binarySearch(int[] arr, int target) {
int count = 0;
// * 1 确定起始下标和结束下标
int startPos = 0;
int endPos = arr.length - 1;
// * 2 确定中间下标,然后和目标数据开始比较
int m = (startPos + endPos) / 2;
// 循环比较
while (startPos <= endPos) {
count++;
// * 3 如果相等.就返回中间下标即可
if (target == arr[m]) {
System.out.println("二分查找 : "+count);
return m;
}
// * 4 如果目标数据大于中间数据 , 结束值不变,起始值=中间值+1, 重新生成中间值,继续比较
if (target > arr[m]) {
startPos = m+1;
}
// * 5 如果目标数据小于中间数据,起始值不变,结束值=中间值-1.重新生成中间值,继续比较
if (target < arr[m]) {
endPos = m-1;
}
m = (startPos + endPos) / 2;
}
// * 6 当起始值大于结束值的时候,说明不存在
System.out.println("二分查找 : "+count);
return -1;
}
// 传统查找方式
public static int search(int[] arr , int num){
int count = 0;
for (int i = 0; i < arr.length; i++) {
count++;
if (arr[i] == num) {
System.out.println("顺序查找 : "+count);
return i;
}
}
System.out.println("顺序查找 : "+count);
return -1;
}
}
练习题：
1.
-
观察下面杨辉三角（前5行）并打印出前N行
二维数组,每个一维数组 都是一行
第一行1列,第二行2列,第三行3列1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
n行m列 = (n-1)行(m-1)列 + (n-1)行m列
public class Test_01 {
public static void main(String[] args) {
test(17);
}
public static void test(int n){
// 1 二维数组存储
int[][] nums = new int[n][];
// 初始化每个一维数组
for (int i = 0; i < nums.length; i++) {
// 初始化长度
nums[i] = new int[i + 1];
// 初始化首元素
nums[i][0] = 1;
// i = nums[i].length - 1
// 初始化尾元素
nums[i][i] = 1;
// 初始化非首尾,第二列开始,倒数第二列结束
for (int j = 1; j < nums[i].length - 1; j++) {
// n行m列 = (n-1)行(m-1)列 + (n-1)行m列
nums[i][j] = nums[i - 1][j - 1] + nums[i - 1][j];
}
}
// 遍历
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[i].length; j++) {
System.out.print(nums[i][j]+" ");
}
System.out.println();
}
}
}
2.
- 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度
- 示例 1 给定数组 nums ={1,1,2}; 函数应该返回新的长度 2,并且原数组 nums的前两个元素被修改为 1,2
- 你不需要考虑数组中超出新长度后面的元素
- 示例 2 给定 nums={0,0,1,1,1,2,2,3,3,4}; 函数应该返回新的长度 5 ,并原数组 nums的前5个元素被修改为
- 0,1,2,3,4 你不需要考虑数组中超出新长度后面的元素
代码：
public static int removeDuplicates(int[] arr){
// 题目得知,数组为升序数组,所以我们只需要比较相邻元素即可
// 类似于冒泡排序.挨着的比较.如果不相等,往前放
// 用于保存新长度,因为最少也有一个元素(都是相等的)
// 还代表下一个元素的下标
int length = 1;
// 遍历 相邻比较
for (int i = 0; i < arr.length-1; i++) {
// 判断是否相等
if (arr[i] != arr[i+1]) {
// 如果不相等,把下一位的值放到length位上
arr[length] = arr[i+1];
// length加一
length++;
}
}
return length;
}
}
