异序二分查找二分查找方程根二分查找重复元素最后一个

Dear 丶 2023-05-31 06:42 4阅读 0赞

原文链接：http://www.cnblogs.com/liyuquan/p/8678237.html  
1 题目1 类二分查找  
1.1 题目  
将有序数组a的后面随机一段一插到数组前面，使用类似二分查找的方法，查找一个元素e。

1.2 解题思路  
将有序数组的后面一部分插到数组前面，使用二分查找查找一个元素。

这样的查找，可以首先定义一个mid代表中间位置。  
随后，首先判断mid所在位置，是在被插到前面数值较大的一段，还是原本数值较小的一段。  
如果在前面较大数值一段，则再判断目标元素是否在这一段中间，在则将高位hi移动到mid，否则移动低位lo到mid  
如果在后面较小数值一段，则再判断目标元素是否在这一段中间，在则移动低位lo到mid，否则将高位hi移动到mid  
判断lo和hi位置的数值是否为目标值，是则返回下标，不是则返回-1  
1.3 Java实现代码  
public static int binSearch(int\[\] array, int n) \{  
int lo = 0;  
int hi = array.length - 1;  
int mid = (lo + hi) >> 1;

while(lo+1 < hi) {
        mid = (lo + hi) >> 1;
        
        if (array[lo] <= array[mid])   //前面一段
            if (array[lo] <= n && n <= array[mid]) 
                hi = mid;
            else lo = mid;
        else 
            if(array[mid] <= n && n <= array[hi]) 
                lo = mid;
            else hi = mid;
    }
    if(array[lo] == n) return lo;
    if(array[hi] == n) return hi;
    return -1;

\}  
1.4 测试结果  
The array:  
7 8 9 11 14 15 2 3 4 5  
Try find 1’s index in array: -1  
Try find 3’s index in array: 7  
Try find 5’s index in array: 9  
Try find 15’s index in array: 5

The array2:  
9 11 14 1 2 3 4 5 6 7  
Try find 1’s index in array2: 3  
Try find 3’s index in array2: 5  
Try find 5’s index in array2: 7  
Try find 15’s index in array2: -1  
2 题目2 类二分查找方程根  
2.1 题目  
已知方程为 x^3-x+4 = 0 的根在 \[-5, 0\] 内，请使用二分查找的求解方法寻找到方程的近似根，要求保留四位小数

2.2 解题思路  
类二分查找方程的根，可以将循环判断条件改变达到目的。

这样的查找，可以首先定义一个mid代表中间位置。  
随后，首先循环判断高位hi减去低位lo是否到达目标精度  
再在循环内部判断高位hi和中间位置mid的函数值是否为正  
为正则说明根不在\[lo, hi\]内，将lo移动到mid位置  
不为正则说明在，将hi移动到mid位置  
返回mid位置  
2.3 Java实现代码  
public static double result\_search(double lo, double hi) \{  
double mid = (lo + hi) / 2;  
while(hi-lo > 0.00001)\{  
mid = (lo + hi) / 2;  
if( f(lo)\*f(mid) > 0 )\{  
lo = mid;  
\} else if( f(hi)\*f(mid) > 0 )\{  
hi = mid;  
\}  
\}  
return mid;  
\}

public static double f(double x)\{  
return x*x*x -x + 4;  
\}  
2.4 测试结果  
Try to search the root of the equation below:  
x^3 -x + 4 = 0  
(Assert there is only one root of the equation)  
\-1.7963  
3 题目3 二分查找最后一个值  
3.1 题目  
实现二分搜索中如果有多个重复的数，返回最后一个，

3.2 解题思路  
利用二分查找找到目标元素出现的第一个和最后一个位置,只需要对于二分查找的退出条件，做一个简单的设定就能得到我们理想的结果，其他都跟二分搜索类似

3.3 Java实现代码  
public static int lastSearch(int\[\] array, int n) \{  
int lo = 0;  
int hi = array.length - 1;  
int mid = (lo + hi) >> 1;

while(lo < hi) {
        mid = (lo + hi + 1) >> 1;
        if(array[mid] > n)
            hi = mid - 1;
        else
            lo = mid;
    }
    if(array[hi] == n) return hi;
    return -1;

\}  
3.4 测试结果  
The array:  
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  
value: 2 3 4 4 5 7 8 9 11 11 11 11 14 15 16 16 16 16  
Try find 1’s last index in array: -1  
Try find 3’s last index in array: 1  
Try find 4’s last index in array: 3  
Try find 11’s last index in array: 11  
Try find 16’s last index in array: 17  
转载于:https://www.cnblogs.com/liyuquan/p/8678237.html