How to resolve the algorithm Binary search step by step in the AArch64 Assembly programming language
How to resolve the algorithm Binary search step by step in the AArch64 Assembly programming language
Table of Contents
Problem Statement
A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm. As an analogy, consider the children's game "guess a number." The scorer has a secret number, and will only tell the player if their guessed number is higher than, lower than, or equal to the secret number. The player then uses this information to guess a new number. As the player, an optimal strategy for the general case is to start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.
Given the starting point of a range, the ending point of a range, and the "secret value", implement a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. There are several binary search algorithms commonly seen. They differ by how they treat multiple values equal to the given value, and whether they indicate whether the element was found or not. For completeness we will present pseudocode for all of them. All of the following code examples use an "inclusive" upper bound (i.e. high = N-1 initially). Any of the examples can be converted into an equivalent example using "exclusive" upper bound (i.e. high = N initially) by making the following simple changes (which simply increase high by 1): The algorithms are as follows (from Wikipedia). The algorithms return the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary one). It is also possible, when the element is not found, to return the "insertion point" for it (the index that the value would have if it were inserted into the array). Recursive Pseudocode: Iterative Pseudocode: The following algorithms return the leftmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the lower (inclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than or equal to the given value (since if it were any lower, it would violate the ordering), or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level. Recursive Pseudocode: Iterative Pseudocode: The following algorithms return the rightmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the upper (exclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than the given value, or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level. Note that these algorithms are almost exactly the same as the leftmost-insertion-point algorithms, except for how the inequality treats equal values. Recursive Pseudocode: Iterative Pseudocode: Make sure it does not have overflow bugs. The line in the pseudo-code above to calculate the mean of two integers: could produce the wrong result in some programming languages when used with a bounded integer type, if the addition causes an overflow. (This can occur if the array size is greater than half the maximum integer value.) If signed integers are used, and low + high overflows, it becomes a negative number, and dividing by 2 will still result in a negative number. Indexing an array with a negative number could produce an out-of-bounds exception, or other undefined behavior. If unsigned integers are used, an overflow will result in losing the largest bit, which will produce the wrong result. One way to fix it is to manually add half the range to the low number: Even though this is mathematically equivalent to the above, it is not susceptible to overflow. Another way for signed integers, possibly faster, is the following: where >>> is the logical right shift operator. The reason why this works is that, for signed integers, even though it overflows, when viewed as an unsigned number, the value is still the correct sum. To divide an unsigned number by 2, simply do a logical right shift.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Binary search step by step in the AArch64 Assembly programming language
Source code in the aarch64 programming language
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program binSearch64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .asciz "Value find at index : @ \n"
szCarriageReturn: .asciz "\n"
sMessRecursif: .asciz "Recursive search : \n"
sMessNotFound: .asciz "Value not found. \n"
TableNumber: .quad 4,6,7,10,11,15,22,30,35
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
mov x0,4 // search first value
ldr x1,qAdrTableNumber // address number table
mov x2,NBELEMENTS // number of élements
bl bSearch
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#11 // search median value
ldr x1,qAdrTableNumber
mov x2,#NBELEMENTS
bl bSearch
ldr x1,qAdrsZoneConv
bl conversion10 // decimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#12 //value not found
ldr x1,qAdrTableNumber
mov x2,#NBELEMENTS
bl bSearch
cmp x0,#-1
bne 2f
ldr x0,qAdrsMessNotFound
bl affichageMess
b 3f
2:
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
3:
mov x0,#35 // search last value
ldr x1,qAdrTableNumber
mov x2,#NBELEMENTS
bl bSearch
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
/****************************************/
/* recursive */
/****************************************/
ldr x0,qAdrsMessRecursif
bl affichageMess // display message
mov x0,#4 // search first value
ldr x1,qAdrTableNumber
mov x2,#0 // low index of elements
mov x3,#NBELEMENTS - 1 // high index of elements
bl bSearchR
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#11
ldr x1,qAdrTableNumber
mov x2,#0
mov x3,#NBELEMENTS - 1
bl bSearchR
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#12
ldr x1,qAdrTableNumber
mov x2,#0
mov x3,#NBELEMENTS - 1
bl bSearchR
cmp x0,#-1
bne 4f
ldr x0,qAdrsMessNotFound
bl affichageMess
b 5f
4:
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
5:
mov x0,#35
ldr x1,qAdrTableNumber
mov x2,#0
mov x3,#NBELEMENTS - 1
bl bSearchR
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc #0 // perform the system call
//qAdrsMessValeur: .quad sMessValeur
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrsMessRecursif: .quad sMessRecursif
qAdrsMessNotFound: .quad sMessNotFound
qAdrTableNumber: .quad TableNumber
/******************************************************************/
/* binary search iterative */
/******************************************************************/
/* x0 contains the value to search */
/* x1 contains the adress of table */
/* x2 contains the number of elements */
/* x0 return index or -1 if not find */
bSearch:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
mov x3,#0 // low index
sub x4,x2,#1 // high index = number of elements - 1
1:
cmp x3,x4
bgt 99f
add x2,x3,x4 // compute (low + high) /2
lsr x2,x2,#1
ldr x5,[x1,x2,lsl #3] // load value of table at index x2
cmp x5,x0
beq 98f
bgt 2f
add x3,x2,#1 // lower -> index low = index + 1
b 1b // and loop
2:
sub x4,x2,#1 // bigger -> index high = index - 1
b 1b // and loop
98:
mov x0,x2 // find !!!
b 100f
99:
mov x0,#-1 //not found
100:
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* binary search recursif */
/******************************************************************/
/* x0 contains the value to search */
/* x1 contains the adress of table */
/* x2 contains the low index of elements */
/* x3 contains the high index of elements */
/* x0 return index or -1 if not find */
bSearchR:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
stp x5,x6,[sp,-16]! // save registers
cmp x3,x2 // index high < low ?
bge 1f
mov x0,#-1 // yes -> not found
b 100f
1:
add x4,x2,x3 // compute (low + high) /2
lsr x4,x4,#1
ldr x5,[x1,x4,lsl #3] // load value of table at index x4
cmp x5,x0
beq 99f
bgt 2f // bigger ?
add x2,x4,#1 // no new search with low = index + 1
bl bSearchR
b 100f
2: // bigger
sub x3,x4,#1 // new search with high = index - 1
bl bSearchR
b 100f
99:
mov x0,x4 // find !!!
b 100f
100:
ldp x5,x6,[sp],16 // restaur 2 registers
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
You may also check:How to resolve the algorithm Price fraction step by step in the Sidef programming language
You may also check:How to resolve the algorithm Execute a system command step by step in the MUMPS programming language
You may also check:How to resolve the algorithm Conditional structures step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Fractran step by step in the BQN programming language
You may also check:How to resolve the algorithm Comments step by step in the IDL programming language