前提:有序 无序是没法用二分法进行搜索查找的
package com.day1;
public class 二分算法 {
public static void main(String[] args){
int[] array={1,2,4,6};
int num=3;
int returnIndex = findAndReturnIndex(array, num);
System.out.println(returnIndex);
}
public static int findAndReturnIndex(int[] array,int num){
int low=0,high=array.length-1,mid=(low+high)/2;
while (low<=high){
if (num==array[mid]){
return mid;
}else if(num<array[mid]){
high=mid-1;
mid=(low+high)/2;
}else if(num>array[mid]){
low=mid+1;
mid=(low+high)/2;
}
}
return -1;
}
}
二分查找法的时间复杂度:
按照最不理想的情况:每次遍历会去掉一半注定不会搜索到的数据
如果是N条数据,则一共需要过滤Log2 N次
即二分查找法时间复杂度为O(log2 N)
