type
status
date
slug
summary
tags
category
icon
password
1、概念
二分查找属于递归查找的一种,其主要思想是将一个有序数组,分为二分,进行递归,反复为之。
2、实际应用
请对一个有序数组进行二分查找{1,8,10,89,1000,1234},输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。
3、思路

4、代码实现
package com.qf.search; import java.util.ArrayList; import java.util.List; public class SeqSearch { /** * 二分查找 * @param args */ public static void main(String[] args) { //有序的数组 int[] arr={1,8, 10, 89, 1000,1234}; int i = seqSearch(arr, 0, arr.length - 1, 1000); System.out.println("查找到的下标位置:"+i); } public static int seqSearch(int[] arr,int left,int right,int findValue){ //跳出循环 if (left>right){ return -1; } //找出中间的位置 int mid=(left+right)/2; //中间的位置与要找的值进行对比 int midValue=arr[mid]; if (midValue<findValue){ //向右查找 return seqSearch(arr,mid+1,right,findValue); }else if (midValue>findValue){ //向左查找 return seqSearch(arr,left,mid-1,findValue); }else{ //相等,找到 return mid; } } }
5、思考题:
{1,8, 10, 89, 1000, 1000,1000,1000,1234} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000.
6、优化实现
package com.qf.search; import java.util.ArrayList; import java.util.List; public class SeqSearch { /** * 二分查找 * @param args */ public static void main(String[] args) { //有序的数组 int[] arr={1,8, 10, 89, 1000, 1000,1000,1000,1234}; List<Integer> integerList = seqSearch2(arr, 0, arr.length - 1, 1000); System.out.println("查找到的下标位置:"+integerList); } public static int seqSearch(int[] arr,int left,int right,int findValue){ if (left>right){ return -1; } //找出中间的位置 int mid=(left+right)/2; //中间的位置与要找的值进行对比 int midValue=arr[mid]; if (midValue<findValue){ //向右查找 return seqSearch(arr,mid+1,right,findValue); }else if (midValue>findValue){ //向左查找 return seqSearch(arr,left,mid-1,findValue); }else{ //相等,找到 return mid; } } public static List<Integer> seqSearch2(int[] arr, int left, int right, int findValue){ List<Integer> list=new ArrayList<>(); if (left>right){ return list; } //找出中间的位置 int mid=(left+right)/2; //中间的位置与要找的值进行对比 int midValue=arr[mid]; if (midValue<findValue){ //向右查找 return seqSearch2(arr,mid+1,right,findValue); }else if (midValue>findValue){ //向左查找 return seqSearch2(arr,left,mid-1,findValue); }else{ //相等,找到 int temp=mid; //向左查找与findValue相等的数值 while (true){ if (temp<left||arr[temp]!=findValue){ break; } list.add(temp); temp--; } //向右查找与findValue相等的数值 temp=mid+1; while (true){ if (temp>right||arr[temp]!=findValue){ break; } list.add(temp); temp++; } return list; } } }
- 作者:程序员小舟
- 链接:https://codezhou.top/article/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。