📄 binarysearch.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>二分搜寻法（搜寻原则的代表）</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 二分搜寻法（搜寻原则的代表）</a></h1>
<h2>说明</h2>
如果搜寻的数列已经有排序，应该尽量利用它们已排序的特性，以减少搜寻比对的次数，这是搜寻的基本原则，二分搜寻法是这个基本原则的代表。<br>
<h2>解法</h2>
在二分搜寻法中，从数列的中间开始搜寻，如果这个数小于我们所搜寻的数，由于数列已排序，则该数左边的数一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的数无需再搜寻，直接搜寻左边的数。<br>
<br>
所以在二分搜寻法中，将数列不断的分为两个部份，每次从分割的部份中取中间数比对，例如要搜寻92于以下的数列，首先中间数索引为(0+9)/2 = 4（索引由0开始）：<br>
<div style="margin-left: 40px;"><span style="font-family: Courier New,Courier,monospace;">[3 24 57 57 </span><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">67</span><span style="font-family: Courier New,Courier,monospace;"> 68 83 90 92 95]</span><br>
</div>
<br>
由于67小于92，所以转搜寻右边的数列：<br>
<div style="margin-left: 40px;"><span style="font-family: Courier New,Courier,monospace;">3 24 57 57 67 [68 83 </span><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">90</span><span style="font-family: Courier New,Courier,monospace;"> 92 95]</span><br>
</div>
<br>
由于90小于92，再搜寻右边的数列，这次就找到所要的数了：<br>
<div style="margin-left: 40px;"><span style="font-family: Courier New,Courier,monospace;">3 24 57 57 67 68 83 90 [</span><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">92</span><span style="font-family: Courier New,Courier,monospace;"> 95] </span><br>
</div>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#include <time.h> <br>#define MAX 10 <br>#define SWAP(x,y) {int t; t = x; x = y; y = t;} <br><br>void quicksort(int[], int, int); <br>int bisearch(int[], int); <br><br>int main(void) { <br> int number[MAX] = {0}; <br> int i, find; <br><br> srand(time(NULL)); <br><br> for(i = 0; i < MAX; i++) { <br> number[i] = rand() % 100; <br> } <br><br> quicksort(number, 0, MAX-1); <br><br> printf("数列："); <br> for(i = 0; i < MAX; i++) <br> printf("%d ", number[i]); <br><br> printf("\n输入寻找对象："); <br> scanf("%d", &find); <br><br> if((i = bisearch(number, find)) >= 0) <br> printf("找到数字于索引 %d ", i); <br> else <br> printf("\n找不到指定数"); <br> <br> printf("\n"); <br><br> return 0; <br>} <br><br>int bisearch(int number[], int find) { <br> int low, mid, upper; <br><br> low = 0; <br> upper = MAX - 1; <br><br> while(low <= upper) { <br> mid = (low+upper) / 2; <br> if(number[mid] < find) <br> low = mid+1; <br> else if(number[mid] > find) <br> upper = mid - 1; <br> else <br> return mid; <br> } <br><br> return -1; <br>} <br><br>void quicksort(int number[], int left, int right) { <br> int i, j, k, s; <br><br> if(left < right) { <br> s = number[(left+right)/2]; <br> i = left - 1; <br> j = right + 1; <br><br> while(1) { <br> while(number[++i] < s) ; // 向右找 <br> while(number[--j] > s) ; // 向左找 <br> if(i >= j) <br> break; <br> SWAP(number[i], number[j]); <br> } <br><br> quicksort(number, left, i-1); // 对左边进行递回 <br> quicksort(number, j+1, right); // 对右边进行递回 <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class BinarySearch {<br> public static int search(int[] number, int des) {<br> int low = 0; <br> int upper = number.length - 1; <br><br> while(low <= upper) { <br> int mid = (low+upper) / 2; <br> if(number[mid] < des) <br> low = mid+1; <br> else if(number[mid] > des) <br> upper = mid - 1; <br> else <br> return mid; <br> } <br><br> return -1; <br> }<br> <br> public static void main(String[] args) {<br> int[] number = {1, 4, 2, 6, 7, 3, 9, 8};<br> <br> QuickSort.sort(number);<br> <br> int find = BinarySearch.search(number, 3);<br> <br> if(find != -1) <br> System.out.println("找到数值于索引" + find); <br> else <br> System.out.println("找不到数值"); <br> }<br>} </pre>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -