- 2020-06-03 05:11
*views 4*- Data structure and algorithm

<> 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

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 2

©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