Java二分法查找_动力节点Java学院整理

网友投稿 248 2023-05-22


Java二分法查找_动力节点Java学院整理

算法

假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.

开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。

令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。

令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,

表示查找不成功。

例:在有序的有N个元素的数组中查找用户输进去的数据x。算法如下:

1.确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。

2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。

3.若a[mid]x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。

算法复杂度分析

时间复杂度

1.最坏情况查找最后一个元素(或者第一个元素)Master定理T(n)=T(n/2)+O(1)所以T(n)=O(logn)

2.最好情况查找中间元素O(1)查找的元素即为中间元素(奇数长度数列的正中间,偶数长度数列的中间靠左的元素)

空间复杂度:

S(n)=n

package com.bjpowernode.test;

public class BinarySearch {

// 查找次数

static int count;

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

System.out.println(searchRecursive(array, 0, array.length - 1, 9));

System.out.println(count);

count = 0;

System.out.println(searchLoop(array, 9));

Systemhttp://.out.println(count);

}

/**

* 执行递归二分查找,返回第一次出现该值的位置

*

* @param array

* 已排序的数组

* @param start

* 开始位置

* @param end

* 结束位置

* @param findValue

* 需要找的值

* @return 值在数组中的位置,从0开始。找不到返回-1

*/

public static int searchRecursive(int[] array, int start, int end,

int findValue) {

// 如果数组为空,直接返回-1,即查找失败

if (array == null) {

return -1;

}

count++;

if (start <= end) {

// 中间位置

int middle = (start + end) / 1;

// 中值

int middleValue = array[middle];

if (findValue == middleValue) {

// 等于中值直接返回

return middle;

} else if (findValue < middleValue) {

// 小于中值时在中值前面找

return searchRecursive(array, start, middle - 1, findValue);

} else {

// 大于中值在中值后面找

return searchRecursive(array, middle + 1, end, findValue);

}

} else {

// 返回-1,即查找失败

return -1;

}

}

/**

* 循环二分查找,返回第一次出现该值的位置

*

* @param array

* 已排序的数组

* @param findValue

* 需要找的值

* @return 值在数组中的位置,从0开始。找不到返回-1

*/

public static int searchLoop(int[] array, int findValue) {

// 如果数组为空,直接返回-1,即查找失败

if (array == null) {

return -1;

}

// 起始位置

int start = 0;

// 结束位置

int end = array.length - 1;

while (start <= end) {

count++;

// 中间位置

int middle = (start + end) / 2;

// 中值

int middleValue = array[middle];

if (findValue == middleValue) {

// 等于中值直接返回

return middle;

} else if (findValue < middleValue) {

// 小于中值时在中值前面找

end = middle - 1;

} else {

// 大于中值在中值后面找

start = middle + 1;

}

}

// 返回-1,即查找失败

return -1;

}

}

以上所述是给大家介绍的java二分法查找_动力节点Java学院整理,希望对大家有所帮助,如果大家有任何疑问请给我留言,会及时回复大家的。在此也非常感谢大家对我们网站的支持!


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Spring Boot中使用jdbctemplate 操作MYSQL数据库实例
下一篇:Java线程同步、同步方法实例详解
相关文章

 发表评论

暂时没有评论,来抢沙发吧~