冒泡排序 + 二分查找 寻找数字
总体思路：
要想查找某一个数字，我们最先想到的就是二分查找，但是二分查找有一个前提，数组的元素必须要是有序的，所以查找数字之前要进行数字排序
冒泡排序
思路
冒泡排序是十分经典的排序方法，首先要知道有n个数字就意味着有n-1趟排序，趟数也决定了后面要进行的判断的次数，再进行判断每一趟排序要判断是否满足升序的条件，要是满足就进行交换前后的数字即可
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flg = true;
}
}
}
}优化
要是数组的元素已经是升序的，这样子的运行效率就不会很好了，所以可以设一个标示量flg，通过判断它的状态，进行代码的优化
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flg = false;//每一趟都要将flg置为false,所以要将flg=false放第一层for循环里面
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flg = true;
}
}
if (flg == false) {
return; // 要是flg还是等于false，就是没交换，说明都满足升序，所以直接return或者break结束最外面的for循环
}
}
}在解决了数组元素有序性的问题之后，我们就可以开始写二分查找了
二分查找
二分查找思路：
给定一个数组，首先求出数组的左右端数字的下标使之分别为l r，接着求出数组的中间元素arr[mid]
image-20220425195232403
接着输入要查找的数字key
1.当arr[mid]>key时，说明key出现在arr[mid]左边，所以需要将 右下标r 进行左移，左移至mid-1处，进入循环再判断，直至 arr[mid]等于key或者 l 与 r 相等退出循环
image-20220425200125512
2.当arr[mid] <key时，说明key出现在arr[mid]右边，所以需要将 左下标r 进行右移，有移至mid+1处，进入循环再判断，直至arr[mid]等于key或者 l 与 r 相等退出循环
image-20220425200856075
image-20220425200950811
3.要是数组中不存在要查找的数字，就直接返回一个-1
小细节
在求中间元素的下标时，可以使用mid=（l+r）/2 ,但是规定mid是int类型的，有可能有超出int表示的范围，使用可以写成mid=l+(r-l)/2 的形式来避免超出int的范围
原理如图，就是将r多出l的部分一切为二，将其加到 l 上即可使两者一样大
image-20220425201712966
最终代码如下
//冒泡排序
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flg = false;//每一趟都要将flg置为false
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flg = true;
}
}
if (flg == false) {
return; // 要是flg还是等于false，就是没交换，说明都满足升序，所以直接return或者break结束最外面的for循环
}
}
}
//二分查找
public static int binarySearch(int[] arr, int key) {
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] > key) {
r = mid - 1;
} else if (arr[mid] < key) {
l = mid + 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 5, 6, 3, 12, 45, 4};
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) { //多组输入要查找的数字
int key = scanner.nextInt();
bubbleSort(arr);//进行冒泡排序
System.out.println(Arrays.toString(arr));//输出排序后的数组
System.out.println(binarySearch(arr, key));
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录