<> Dichotomy search

notes : The title comes from 《 Zhejiang University - data structure 》 curriculum , The implementation of binary search algorithm .

<> Function interface definition
Position BinarySearch( List L, ElementType X );
among List The structure is defined as follows :
typedef int Position; typedef struct LNode *List; struct LNode { ElementType
Data[MAXSIZE]; Position Last; /* Save the position of the last element in the linear table */ };
also L Is a linear table passed in by the user , among **ElementType Elements can be >,==,<** Compare , And the topic ensures that the incoming data is incremental and orderly . function
BinarySearch To find X stay Data Position in , Array subscript ( be careful : Element from subscript 1 Start storage ). Return subscript if found , Otherwise, a special failure flag is returned NotFound.

<> Sample test program (C Language version )##
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 #define NotFound 0
typedef int ElementType; typedef int Position; typedef struct LNode *List;
struct LNode { ElementType Data[MAXSIZE]; Position Last; /* Save the position of the last element in the linear table */
}; List ReadInput(); /* Referee realization , No details . Element from subscript 1 Start storage */ Position BinarySearch( List L,
ElementType X ); int main() { List L; ElementType X; Position P; L =
ReadInput(); scanf("%d", &X); P = BinarySearch( L, X ); printf("%d\n", P);
return 0; } /* Your code will be embedded here */
<> sample input 1:
5 12 31 55 89 101 31
<> sample output 1:
2
<> sample input 2:
3 26 78 233 31
<> sample output 2:
0
<> Program code :
Position BinarySearch( List Tbl, ElementType K ) { if(Tbl==NULL) return
NotFound; int low=1,high=Tbl->Last; int mid; while(low<=high)//low Must be less than or equal to high
Marked as follows 1,2,3 The subscript to be queried is 1 Of , The first time is to compare the subscript 2 Of , Inconformity high It becomes 1, If you write low<high It will return the wrong result {
mid=(low+high)/2; if(Tbl->Data[mid]==K) return mid; else if(Tbl->Data[mid]>K)
high=mid-1; else low=mid+1; } return NotFound; }
## The test result is consistent with the result of the subject judgment

## Binary search summary :

*
concept
Binary search is also called half search (Binary Search), It is an efficient search method . however , Half search requires the linear table to adopt the sequential storage structure , And the elements in the table are ordered by keywords .
The algorithm makes full use of the order relations among elements , Adopt divide and conquer strategy , Can be used in the worst case O(log
n) Complete search task . Its basic idea is , take n The elements are divided into two parts with approximately the same number , take a[n/2] And the x Make a comparison , If x=a[n/2] Then find x, Algorithm termination . as
fruit x less than a[n/2], Then we just need to a Left half of x( It is assumed that the array elements are arranged in ascending order ). If x greater than a[n/2], Then we just need to a Right of Half continue searching x.
*
Search process
first , Suppose the elements in the table are arranged in ascending order , Compare the key of the middle position record of the table with the search key
, If the two are equal , Search succeeded ; Otherwise, use the middle position record to divide the table into front , Last two sub tables , If the key of the intermediate location record is greater than the search key , Then further find the previous sub table , Otherwise, further search the next sub table . Repeat the above process , Until a record that meets the criteria is found , Make the search successful , Or until the child table does not exist , Failed to find at this time .

*
Algorithm requirements
1, Linear table must adopt sequential storage structure
2, Elements in the table are ordered by key words ( Ascending or descending )

*
Number of comparisons
Calculation formula :a<log2n<b(a,b,n Is a positive integer )a<log2n<b (a,b,n Is a positive integer )a<log2n<b(a,b,n Is a positive integer )
When the sequence table has n When keywords :
When lookup fails , At least compare a Subkey ; When the search succeeds , The maximum number of comparison keywords is b.
be careful :a,b,n All positive integers .

*
Python Source code
def bin_search(data_list, val): low = 0 # Minimum subscript high = len(data_list) - 1 #
Maximum subscript while low <= high: mid = (low + high) // 2 # Middle number subscript if data_list[mid] ==
val: # If the middle subscript is equal to val, return return mid elif data_list[mid] > val: # If val To the left of the middle ,
move high subscript high = mid - 1 else: # If val To the right of the middle number , move low subscript low = mid + 1 return #
val non-existent , return None ret = bin_search(list(range(1, 10)), 3) print(ret)
* C/C++ Recursive implementation #include<iostream> using namespace std; int
a[100]={1,2,3,5,12,12,12,15,29,55};// Number in array ( From small to large ) int k;// Number to find int found(int
x,int y) { int m=x+(y-x)/2; if(x>y)// No answer found after searching , return -1 return -1; else {
if(a[m]==k) return m;// find ! Return to position . else if(a[m]>k) return found(x,m-1);// To the left else
return found(m+1,y);// To the right } } int main() { cin>>k;// Enter the number to find c Language cin Replace with scanf that will do
cout<<found(0,9);// From array a[0] reach a[9]c Language cout Replace with printf that will do return 0; }
## Function runtime timer template
#include <iostream> #include <time.h> //For using the system Timer #include
<stdlib.h> using namespace std; clock_t start, stop; //Define the start and
stop of the timer int PrintN(int n) { int i = 0; for (i; i < n; i++) {
std::cout << i << endl; } return 0; } int main() { int n; std::cin>>n; start =
clock(); PrintN(n); stop = clock(); double duration = ((double)(stop - start))
/ CLK_TCK; //To calculate the time that this function used std::cout <<
duration << endl; system("PAUSE"); //Pause the system for a moment return 0; }

Technology
©2019-2020 Toolsou All rights reserved,
Python Basic knowledge and notes 2021 year 1 Monthly programmer salary statistics , average 14915 element GDOI2019 travels C++ Standard library What should I do if I suddenly encounter a question I can't answer during the interview ?2021 year 2 Monthly programmer salary statistics , average 15144 element college examination for the self-taught An overview of Marxism use C++ I want to talk to you “ Prototype mode ” ( copy / copy constructor ) How to use it quickly html and css Write static page Bitcoin in ten years ,VDS Opportunity or fraud