Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

MSP430 assembly language BACKGROUND: BINARY SEARCH A sorted list can be searched very efficiently for a number using a binary search for a target value.

image text in transcribed

MSP430 assembly language

BACKGROUND: BINARY SEARCH A sorted list can be searched very efficiently for a number using a binary search for a target value. The binary search checks the middle value and disregards the half of the list on each iteration until it finds the target value. First, the low and high index values are determined. The value at the midpoint index is checked. If that value is greater than the target value, the top half of the list does not need to be searched, and the high index is set to the midpoint index. If the value at the midpoint index was less than the target value, the low half of the index does not need to be searched, and the low index is set to the midpoint index. The search is repeated until the target value is found at an index Example: goal value=7, first search index low=0, high = 10, check value at index 5:10>7 next search index low-0, high-5, check value at index 2: 447 next search index low-:2, high-5, check value at index 3, 7 =7. Goal value found, index is 3. values 1 347 9 10 12 17 19 21 26 index 02 3 4 5 6 7 89 10 ASSIGNMENT A previous lab performed a bubble sort of a list of numbers. This assignment starts from the assumption of a sorted list, and uses a binary search to find the index of the goal number. You will write a main program (about 10 lines) and a subroutine (about 20 lines). Using assembler directives, place te ist of 1 numbers into memory with a label. The last number in the list should also have a label. Reserve room in memory for the gol value. Reserve room in memory for the index of the goal value The main program (main) will load registers for passing parameters to the subroutine (R5 low address, R6 high address, R7-goal number). After the return from the subroutine the main program should determine if the search is complete, which is when the low and high search addresses are the same. Then the main program should find the index and put it in the reserved memory location for index The subroutine (binary) will take as input the low and high addresses of the current search range and return the updated search range by changing either the low or high address (or both!). It should use the binary algorithm shown in the example above. The subroutine should return the same address in high and low addresses when the target value is found. The subroutine should also not "interfere" with any registers. If it uses any registers more than R5-R7, it should push those registers at the beginning of the subroutine and pop them at the end. Test your program by putting different goal values in the "goal" memory location and see that the correct index is put in memory by the program. Note that there is no "divide" command in assembly language, but there is an casy way to divide a binary number by 2 using the rra command

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Security XI Status And Prospects

Authors: T.Y. Lin, Shelly Qian

1st Edition

0412820900, 978-0412820908

More Books

Students also viewed these Databases questions