Related questions

Mips (assembly) - binary search problem - load not aligned for address of middle array element?

2022-05-04 10:16 EladO O imported from Stackoverflow 
        .text
        j main
        
binary_search:       
        slt $t0, $a2, $a1 # if last < first, $t0 = 1
        beq $t0, $zero, check_mid # if first > last, proceed to return -1   
    
        addi $v0, $zero, -1
        jr $ra # exit with returned argument
        
check_mid:
        # saving address to stack
        addi $sp, $sp, -4
        sw $ra, 4($sp)
             
        sub $t1, $a2, $a1 # last - first
        srl $t1, $t1, 1 # (last - first) /2
     
        add $t2, $a1, $t1 # $t2 is referrencing the mid index of the array
        lw  $t3, 0($t2) # $t3 is the mid element of the array
        
        bne $t3, $a0, check_higher
    
        add $v0, $t2, $zero # $v0 is the index of the wanted element
        
        lw $ra, 4($sp)
        addi $sp, $sp, 4
        
        jr $ra # exit with returned argument
    
check_higher: 
        slt $t0, $t3, $a0 # if arr[mid] < x, $t0 is 1
        bne $t0, $zero, check_lower              
    
        addi $t1, $t1, -4 # mid = mid - 4
        jal binary_search # recursion call                
     
check_lower:
        addi $t1, $t1, 4 # mid = mid + 4
         jal binary_search # recursion call            
                      
main:
        addi $a0, $zero, 64
        addi $a1, $zero, 0
        addi $a2, $zero, 28
        jal binary_search

So this is my code so far. as far as I can see it I'm pretty much done with the code, unless I didn't take care well enough of saving/loading returning addresses from the stack, but that's not my main concern right now.

What I'm trying to figure out, is how do I reach the middle offset/element of the array? because executing this code will bring me the error: "line 39: Runtime exception at 0x00400028: fetch address not aligned on word boundary 0x0000000e" (line 39 is this line: lw $t3, 0($t2) # $t3 is the mid element of the array)

1 answer

  • answered 2022-05-04 11:53 Peter Cordes

    It looks like you're working with byte offsets instead of indexes for words. That's fine and good (instead of redoing left-shifting every time you use the address), but it means that a right shift won't truncate to a word offset, it can shift a bit into the byte-within-word part of the address, the low 2 bytes. Unlike in C if you did mid = (hi-lo)>>1; which would simply shift a bit out the bottom of the value.

    srl $t1, $t1, 1 can thus produce an odd halfword address, instead of truncating down to an aligned word address.

    You could and with -4, i.e. 0xfffffffc to clear those address bits after shifting, but MIPS can't do that in one instruction because andi zero-extends its immediate. If your array really is known to be smaller than 64KiB and at a very low address close to zero (so the 0x0000000e you tried to deref wasn't also a separate bug of getting adding a small offset to a NULL pointer), you could andi with 0x0000fffc to truncate an address. Or do that on an offset before adding it to an actual address if you're working with offsets instead of actual pointers.

    Of course you could just li $t9, -4 once before your loop and use that, but you're using recursion instead of a more efficient loop. So I guess you don't care about efficiency anyway and could just do an extra li right before you want to and. (addiu can materialize a -4 in one instruction, unlike ori.)

    Or the other way would be to right shift the bits you want to discard all the way out of the register, and then to a left shift to bring you data back to where you want it. mid = ((hi-lo)>>3) << 1;

    Also you have other bugs, like falling off the bottom of your function after the jal binary_search in check_lower: returns. You either need to reload $ra and return in those paths, or optimize the tail-call into a j or b after reloading $ra, not jal / reload $ra / jr $ra.

    Same for the jal in check_higher:; you don't want to fall through into check_lower, that would end up checking both sides for O(N) total runtime, not O(log N).

    But those are all things you should debug by single-stepping with a debugger, and separate from the interesting indexing problem of right-shift creating an odd-halfword address when doing binary search in asm with word addresses or byte offsets.

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum

See also questions close to this topic

  • How to get pass an array through a function with a user input?

    I want to ask the user for the size of a 2D array arr[][], but also pass it through the function initializeArray. However, if I pass it through the function, I would have to have a size declarator for col, which doesn't allow the user to enter their own value for the size

      #include<iostream>
  using namespace std;

  void initializeArray(arr[][10], int N);

  int main() {
      int N;
      cout << "enter an array size: ";
      cin >> N;
      int arr[N][N];

      initializeArray(arr, N); // I get an error here
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++)
              cout << arr[i][j] << " ";
          cout << endl;
      }
 }

  void initializeArray(int arr[][10], int N) {
      for(int i = 0; i < N; i++)
          for(int j = 0; j < N; j++)
              arr[i][j] = 0;
  }

    The only solution I found was the make arr[][] a global array, but in that case, I would have to still declare the size parameters, and I want the user to enter whatever they want. Is there another way to fix this?

  • Two-dimensional array C++

    Problem: Write a program of a two dimensional integer array of exactly four rows and four columns, and find the sum of the integers each row of the array as well as determine the smallest inputted element/data in the array. The user will input the elements. Display the elements in tabular form. Make the program user friendly. Use a Class and a member function for the process involve.

  • Pass Associative Array from Symfony Controller to Twig and JavaScript

    So, I have 2 arrays that I've combined into one array after making sure they're the same length as such.

    //Fetching Ratings for All Coaches & Making a Key, Value Associative Array with Coach id as Key and Rating as Value
        $coaches = $coachRepository->findAll();
        $rating = $coachRepository->findRatingByCoach();
        //Array of coach IDs
        $id_array = array();
        foreach ($coaches as $c){
            $id_array[] = $c->getId();
        }
        $combined = array_combine($id_array, $rating);

    Now I want to pass this key, value array to Twig template and JavaScript. I'm currently doing this

        return $this->render('...', [
        ..., 'combined'=>$combined
    ]);

    And I'm accessing the array in Twig as such

                {% for key, value in combined %}
                {{ key }} - {{ value }}
            {% endfor %}

    And I'm getting this error.

    Object of class App\Entity\Coach could not be converted to string

    Looking at the Stack Trace I can see that the array combined is being passed in this form.

    'combined' => array(object(Coach))

    After a bit of debugging it turns out that I thought the issue was with the $id_array when in fact it's the $rating variable that's presenting an issue. I'm not sure why but I'm getting a single float value. I fixed the issue by changing how I'm fetching the $rating, now instead of using a QueryBuilder to get it from the DB, I'm getting it from list of Coaches as such

     //Array of coach IDs and array of Ratings
        $id_array = array();
        $rating_array = array();
        foreach ($coaches as $c){
            $id_array[] = $c->getId();
            $rating_array [] = $c->getRating();
        }

    Even if I set the array

  • MIPS Assembly - how to calculate squre of n recursively

    I want to write a program that calculates the square of n using recursively based on the equation n^2 = (n - 1)^2 + 2(n - 1) + 1 But I don't know how to write the nonbasecase part. Can anyone help?

    A python program would be

    def square(n) {
    if (n==0):
        return 0
    else:
        return square(n-1) + 2*(n-1) + 1 
}

    Here is what I got so far.

    start:      
        li  $a0, 0x0003     #$a0 contains the number to be squared              
        jal square          # recursive call
        
square:     
        subi $sp, $sp, 8    # decrement the stack pointer $sp
        sw  $ra, 4($sp)     # push the return address register $ra
        sw  $a0, 0($sp)     # push argument register $a0
        li  $t0, 0x0001     # load $t0 with 1 as part of test for base case
        bne $a0, $t0, nonbasecase   # branch if not the base case
        li $v0, 0x0001      # return base result in $v0
        addi $sp, $sp 8     # recover stack space 
        jr $ra          # jump to return address in $ra

nonbasecase:    
       #not sure how to write when it is not the base case


        jr $ra          # jump to contents of return address register $ra
  • Arduino Inline ASM

    Hello i am trying to preapre some inline asm codes for my experiment, here is my .ino, how can i start to change this code to inline asm any help or suggestion?

        const int buttonpin = 2;
const int ledpin = 13;
int tracker = 0;
int buttonstate = 0;

void setup() {
  pinMode(ledpin, OUTPUT);
  pinMode(buttonpin, INPUT_PULLUP);
  Serial.begin(9600);
}

void loop() {

  buttonstate = digitalRead(buttonpin);


  if (buttonstate == LOW) {
    tracker++;
   
    if ( (tracker % 3) == 0) 
    { 
      digitalWrite(ledpin, HIGH);

     }
     else
     {
    digitalWrite(ledpin, LOW);
  }
  }
 Serial.println(tracker);
delay(100);
}
  • Purpose of bitwise operation in this example

    In the following function, I am having trouble understanding the purpose to the bitwise operation:
    outb(0x3D5, (uint8_t) (pos & 0xFF));
    pos is a uint16_t variable. Whats the purpose of the bitwise & with simply 8 bits of 1. The & operation would just compare this value with 8 bits of 1s, which to my knowledge, would just result in the same value. How does this operation change the value of pos?

    For background if it is important, the function outb is intended to move the value of the right argument into the register indexed by the port (left argument). In this case, pos is a position in VGA video memory. The function outb uses inline assembly and the assembly function out

  • united state university assignment CST 237, Computer Architecture, Spring 2022 Exam2 
       .data

 #someone hire me on fiver and then get code without paying
 

mainfloat: .float  0.4330125 
firstfloat: .float  3.14 
floatg: .float  2 
lativemsg: .asciiz "The circumference of the circle with radius = "
 msg7: .asciiz "\n The area of the circle with radius = "
 firstmainmsg: .asciiz "Enter value "
 secondmsg: .asciiz "Enter shape value "
 donemsg: .asciiz "The perimeter of the triangle with side = "
 lastmsg: .asciiz " meters is "
 msg4: .asciiz  " meters." 
  msg5: .asciiz "\n The area of the triangle with side = "
 
.globl main

.text
main:
 
la $a0,secondmsg
li $v0,4
syscall           #printing msg


li $v0,5         #get input
syscall

beq $v0,2,Tri           #checking for triange and circle
beq $v0,1,Circle

Circle:

la $a0,firstmainmsg     #priting 
li $v0,4
syscall      


 
li $v0,6           #get input
syscall  
  
lwc1 $f10,firstfloat        #getting values
lwc1 $f8,floatg    
 
mul.s $f10,$f0,$f10        #implementing formula
mul.s $f10,$f10,$f8      
  
    
      
la $a0,lativemsg             #priting
li $v0,4
syscall           
           
mov.s $f12,$f0
li $v0,2
syscall              
             
  la $a0,lastmsg
li $v0,4
syscall                
                
mov.s $f12,$f10
li $v0,2
syscall                   

la $a0,msg4
li $v0,4
syscall                                                  
                                                                                                  
 
la $a0,msg7
li $v0,4
syscall                                                                                                                                                                                                    
   
mov.s $f12,$f0
li $v0,2
syscall
  • how can i convert my swap function from C to mips32 code?

    Ihave this function:

    void swap(int i, int j){
int temp=v[i];
v[i]=v[j];
v[j]=temp;
}

    where i and j are elements from a global array v[]

    I have written this code in mips thus far but the array stays the same and nothing changes:

    swap:                           # swap entry point
sll $t3,$a0,2                   
sll $t4,$a1,2                  
add $t3,$gp,$t3                
add $t4,$gp,$t4
lw $t0,0($t3)                    #t0=v[i]
lw $t1,0($t4)                    #t1=v[j]  
sw $t0,0($t4)
sw $t1,0($t3)
        jr      $ra             # return to caller

    where $a0=i and $a0=j

    Thanks in advance

  • Pull every nth group of rows spilled from a single cell

    I am after a way to pull a consistent group of rows with an equal spacing between each.

    Example: My data range is in A3:A250. I'd like to pull A3:A10,A15:A22,A27:A34,A39:A46, etc. through to the end of the dataset at A250. So, I am pulling 7 rows each time, with a consistent gap of 5 cells between each set of pulled row sets.

    Requirements: I need this formula to all sit within one cell at the top of the data, and spill down to the whole data range, this is because the data will vary in length.

    I am aware of the =OFFSET functionality, and can use =OFFSET(A:A,(ROW()-1),0,7) which will pull the first 7 cells, although (unless I'm mistaken) I'd need to fill this formula down for it to pull the whole range. Is there a way for me to put this in once at the top (in B1 for example) and have it fill for the whole range?

    I am using Excel for MSO 365.

    Thanks!

  • Excel VBA: Loop and finding multiple values in a range then copying the offset cells in the same range in a categorized list in another worksheet

    I am in need of help with looping through a range (In this case Column "C") and finding 5 specific words (Sort, Set, Shine, Standardize, and Sustain) and then offsetting one row below the found value and copying that value to a categorized list on another sheet. To add complexity eliminating duplicate comments and blanks if possible would be great!

    This is an imported form to my workbook and i am trying to create a quickly generated list of each comment under each specific word so that i can then copy into a report.

    Any help would be greatly appreciated!!!

    Picture of excel list

  • excel vba moving the offset to start of the range if exist (functional way of writing)

    Goal is to identify the start of the region value and it will be used in offset.

    1. Input will be dynamic
    2. Row length is not fixed.
    3. Only criteria is region begin and end, but it may exist or not (see the sample input below)
    Criteria Values
    Sample Input 1 to 10
    Region begin 4
    Region end 7

    I have written the following code in procedural way, is there a better functional way of writing the following code for better management and readability?

    Sub findBorder()
    Dim myrange As Range
    Dim rCell As Range
    
    ' (1 2 3 4 5 6 7 8 9 10)
    Set myrange = Range("D1:D10")
    Dim mark_region_begin As Integer
    Dim mark_region_end As Integer
    
    Dim mark_region_after_begin As Integer
    Dim mark_region_before_end As Integer
    
    Range("F1").Value = ""
    Range("F2").Value = ""
    Range("F3").Value = ""
    
    ' Find in bewteen and including 4 & 7
    For Each rCell In myrange:
        If rCell.Value = 4 Then
            mark_region_begin = rCell.Row
        ElseIf rCell.Value > 4 And rCell.Value < 7 Then
            If mark_region_after_begin = 0 Then
                mark_region_after_begin = rCell.Row
            End If
            mark_region_end = rCell.Row
        ElseIf rCell.Value = 7 Then
            If mark_region_begin = 0 Then
                mark_region_begin = rCell.Row
            End If
            mark_region_end = rCell.Row
        End If
    Next rCell
    
    If mark_region_begin = 0 Then
        mark_region_begin = mark_region_after_begin
    End If
    
    Range("F1").Value = mark_region_begin
    Range("F2").Value = mark_region_after_begin
    Range("F3").Value = mark_region_end
    
End Sub

    Sample input: enter image description here

    In the following sample input, The column E is sorted, and the data in the range between -0.15 to +0.15 will be selected.

    A B C D E
    4190.65 4227.6 4332.717 19.79 -7.05
    721.05 734.65 741.9 12.25 -6.80
    4273.05 4303.5 4420.3 14.89 -6.60
    1132.25 1150.3 1180.75 2.56 -6.54
    1134.55 1140.6 1168.317 22.12 -6.47
    4015.5 4030.4 4135.3 13.94 -6.34
    597 608.6 617.8 4.19 -5.82
    1355 1360.95 1385.317 2.95 -5.60
    2104.1 2116.55 2158.483 6.93 -5.49
    808.9 816.45 830.8167 1.54 -5.39
    367.2 370 377.0667 7.87 -5.29
    347.75 349.65 357.2167 3.28 -5.18
    7045.1 7178.65 7178.633 11.76 -5.03
    515.9 521.95 529.3 4.05 -4.91
    2002.4 2026.3 2071.267 4.24 -4.88
    100.5 101.2 102.7 2.36 -4.78
    116.95 117.7 119.4833 17.83 -4.75
    460.85 463.1 468.8 2.21 -4.69
    2326.1 2343.6 2379.25 8.58 -4.49
    193.8 196.25 198.85 0.71 -4.49
    2277.7 2290.4 2327.683 6.18 -4.39
    711.25 714.5 726.75 3.32 -4.34
    14285.7 14354.5 14580.02 5.18 -4.33
    6310.1 6365.15 6456.383 4.51 -4.31
    119.2 120.65 122.6167 12.48 -4.31
    80.8 81.3 82.96667 1.11 -4.29
    1537.25 1549.45 1585.133 6.86 -4.23
    778.05 785.75 797.9333 7.22 -4.18
    459.85 461.55 468.8 -0.05 -4.15
    2406.15 2413.75 2457.283 2.79 -4.15
    243 244.7 249.05 0.55 -4.14
    742.6 751.3 759.9167 7.98 -4.13
    310.75 312.85 317.8167 0.81 -4.13
    108.05 108.7 110.8167 5.24 -4.10
    912.7 922 932.5667 3.01 -4.06
    626.1 629.55 637.3666 8.14 -3.89
    3767.4 3800.95 3871.116 11.39 -3.88
    4333.15 4348.5 4406.033 6.91 -3.88
    1444.55 1449.9 1469.15 4.14 -3.83
    2303.15 2324.6 2347.9 8.44 -3.77
    1036.05 1043.35 1058.967 1.72 -3.77
    685.9 688.6 696.3499 1.75 -3.74
    2242.95 2263.4 2292.116 1.84 -3.73
    1492.35 1500.3 1527.467 10.11 -3.68
    2436.5 2488.7 2506.85 6.64 -3.64
    1795.85 1804.5 1821.783 2.37 -3.62
    972.2 978.9 994.8667 2.7 -3.61
    2686 2696.85 2728.3 4.57 -3.59
    1620.15 1627.35 1649.75 2.06 -3.55
    145.5 146.45 150.0667 2.77 -3.46
    419.45 421.6 427.1 4.48 -3.31
    196 203.8 204.1333 3.73 -3.29
    266.5 268.25 271.6167 0.79 -3.28
    3978.4 4003.5 4041.25 3.48 -3.27
    338.5 339.55 343.5 1.63 -3.26
    1899.3 1909.65 1934.583 0.23 -3.21
    534.15 539.1 547.9167 1.77 -3.20
    221.25 223.1 227.0167 1.07 -3.10
    3371 3412.65 3443.45 2.25 -3.09
    3083.1 3102.8 3128.1 5.42 -3.07
    25129.5 25237.55 25722.35 3.99 -3.06
    2687 2703.05 2728.333 2.2 -3.04
    113 114.1 115.4833 0.59 -3.03
    3484.1 3498.85 3548.533 1.29 -3.00
    694.55 698.25 706.7333 3.17 -2.99
    1962.45 1978.05 2000.167 4.74 -2.99
    1339.55 1346.7 1359.667 3.89 -2.98
    229.2 231.8 234.0333 1.22 -2.95
    624.2 626.9 634.05 3.33 -2.93
    7372.05 7416.9 7516.267 0.64 -2.92
    367.7 369.35 373.6167 1.98 -2.88
    109.45 109.95 111.1833 1.79 -2.87
    1252.2 1258.3 1267.833 8.8 -2.81
    392.65 395.65 399.9333 4.08 -2.79
    323.75 326.95 330.4167 1.12 -2.77
    8446.35 8582.25 8631.017 1.04 -2.76
    706.25 709.95 718.1667 1.1 -2.76
    1320.6 1331.85 1349.333 13.81 -2.76
    476.6 479.3 484.4667 4.82 -2.75
    761.3 767.35 779.0334 3.47 -2.75
    2152.05 2173.95 2193.667 0.9 -2.75
    716.3 718.95 727.75 0.29 -2.72
    110.8 111.4 112.9333 2.11 -2.71
    2405.95 2417.15 2451.2 2.72 -2.67
    69892.8 70396.05 71025.88 3.6 -2.63
    16210 16280.9 16376.4 13.1 -2.59
    6507.75 6526.7 6585.333 3.54 -2.56
    2197 2210.75 2229.35 5.88 -2.55
    718.25 722.6 727.2333 1.12 -2.54
    258.15 259.85 263.1833 2.28 -2.54
    710.3 713.65 719.9333 3.07 -2.52
    16600 16722.15 16797.17 -0.74 -2.51
    366.1 369.55 373.1 5.47 -2.47
    825 827.85 837.8167 -0.17 -2.47
    113.95 114.3 115.45 3.82 -2.43
    517.75 521.65 526.95 -0.04 -2.42
    93.95 94.95 95.9 3.31 -2.42
    35145.95 35308.15 35598.03 14.74 -2.38
    123.2 123.7 125.0167 2.39 -2.37
    894 899.85 906.1833 5.82 -2.36
    3194.8 3203 3231.267 4.6 -2.35
    156.4 157.05 158.6333 -0.87 -2.33
    14110 14168.85 14268.67 6.25 -2.33
    1631.9 1640.3 1653.017 3.86 -2.32
    304 305.85 308.5333 -1.25 -2.32
    896.2 901.6 907.6667 7.99 -2.31
    2742 2791.2 2808.5 3.55 -2.30
    433.75 438.5 443.45 -0.87 -2.24
    572.85 578.9 583.2167 0.93 -2.21
    2466.35 2493.85 2511.3 6.7 -2.20
    2199.85 2204.25 2223.95 2.93 -2.20
    2008.9 2022.05 2035.367 2.78 -2.19
    442.2 448 451.7333 -1.46 -2.19
    199.4 200.05 202.0333 4.69 -2.18
    129.75 130.6 131.8667 4.3 -2.17
    2666.05 2691.8 2711.833 3.22 -2.16
    950.45 958.45 964.05 3.02 -2.15
    16643.2 16702.5 16827.82 25.56 -2.15
    254.85 257.85 260.7 -1.22 -2.15
    724 727.05 733.55 2.57 -2.14
    982 986 997.45 9.45 -2.12
    750.2 757.7 764.95 0.06 -2.11
    421.25 424.05 428.95 1.21 -2.11
    3815.25 3842.65 3881.384 -1.83 -2.07
    603.1 609.25 611.9667 0.52 -2.05
    255.2 258.35 260.4667 2.8 -2.03
    540.6 543.45 548.0167 2.05 -2.03
    802.5 805.9 812.9333 4.24 -2.02
    2420 2435.65 2454.883 4.32 -1.99
    18000 18106.2 18219.4 4.03 -1.98
    276.45 279 281.5334 2.91 -1.94
    2007.65 2018.05 2031.683 3.32 -1.93
    507.25 512.55 515.4167 2.74 -1.90
    723 727.75 734.4 1.88 -1.88
    1040.45 1049.45 1056.6 3.19 -1.85
    566.2 569.4 572.4666 2.48 -1.84
    2275 2300.25 2313.417 -0.77 -1.82
    54.8 55.25 55.93333 0.2 -1.77
    366 367.75 370.5333 1.82 -1.74
    39067.45 39122.3 39462.92 5.62 -1.73
    1776.35 1781.6 1793.317 3.87 -1.69
    1205.25 1217.45 1224.033 3.62 -1.67
    1248.4 1254.4 1265.267 0.87 -1.67
    1595.25 1598.65 1611.25 4.68 -1.60
    131.6 132.2 133.5333 -0.9 -1.56
    1559.9 1566.7 1576.75 -2.17 -1.56
    1258.8 1265.05 1282.95 7.18 -1.47
    1010.6 1015 1022.533 0.25 -1.38
    3471.25 3483.45 3507.783 3.35 -1.29
    198.6 200.2 201.8667 5.44 -1.28
    1620.7 1629.5 1640.817 2.78 -1.26
    4034.2 4053.5 4088.75 -1.13 -1.25
    178.05 179.95 182.95 12.54 -1.21
    258.2 259.3 260.9 8.69 -1.18
    834.4 838.8 842.7334 -2.55 -1.10
    360.55 363.8 365.4666 0.93 -1.09
    529.5 530.9 535.1334 4.22 -1.05
    4102.2 4125.15 4159.05 0.64 -1.02
    243.75 245.9 248.15 0.9 -0.90
    93.9 94.55 95.56667 0.47 -0.84
    668.5 674.3 680.2 -0.89 -0.81
    2086.2 2099.35 2110.583 8.33 -0.81
    338.85 343.95 344.25 2.12 -0.75
    818 825.95 831.2834 3.78 -0.73
    490.75 493.8 496.7 0.7 -0.71
    898.2 911 912.0334 1.71 -0.68
    823.1 829.9 834.7834 4.77 -0.62
    45142.85 45377.95 45544.61 5.69 -0.61
    1270.9 1279.05 1281.983 0.57 -0.53
    516.25 519.8 524.5667 1.34 -0.52
    3914.1 3943.4 3963.833 3.67 -0.52
    125.6 126.4 127.0667 0.27 -0.51
    764.15 768.5 771.2166 1.87 -0.47
    3451.15 3480.1 3497.316 0.55 -0.30
    1067.5 1080.7 1081.767 1.77 -0.28
    638.2 642.85 644.65 1.74 -0.26
    1536.45 1542.05 1550.75 2.02 -0.13
    401 406.15 407.6167 2.21 -0.09
    2267.2 2296.15 2313.85 5.95 -0.03
    270.7 272.3 273.4833 0.48 -0.02
    156.5 158.1 158.4167 0.87 0.00
    186.9 187.9 188.65 0.89 0.03
    1572.2 1585.25 1590.95 0.02 0.15
    1206.15 1214.65 1219.1 1.75 0.23
    1770.5 1783.5 1794.05 6.99 0.24
    116.35 117.35 118.95 4.16 0.25
    4690 4744.95 4754.633 0.35 0.29
    1031 1039.4 1042.133 3.65 0.41
    151.3 152.5 153.5667 1.62 0.63
    157.6 158.8 159.5 2.88 0.92
    486.2 497.4 495.3333 -9.39 1.67
    233.65 237.9 237.0833 4.66 2.65
    208.4 213.8 212.3833 1.64 2.66
    158.45 162.75 161.5667 -1.41 3.69
    3344.9 3395.5 3447.267 11.16 3.71
    168.4 176.5 174.7667 19.57 5.77
  • Binary search with recursion c#

    I got stuck with my binary search method and I don't really know what I'm doing.

    At this moment I got

    1 Error (CS0161) not all code paths return a value

    int low = 0;
int high = cities.Length;

static int BinarySearch(City[] cities, int key, int low, int high)
{
    int mid;

    if (low > high)
        return -1; //Sökning EJ hittad

    mid = low + high / 2;

    if (key == cities[mid].temp)
        return mid; //Sökning Hittad!
    else if (key < cities[mid].temp)
        BinarySearch(cities, key, low, mid - 1);
    else
        BinarySearch(cities, key, mid + 1, high);
}

    ...searching for temperature with input from user.

    Console.WriteLine("\n\tBINARY SEARCH\n");
do
{
    Console.Write("Search temp:");
    loop = true;
    str = Console.ReadLine();
    try
    {
        key = Convert.ToInt32(str);
        
         
        index = BinarySearch(cities, key, low, high);
        if (index == -1)
        {
            Console.WriteLine($"Couldn't find any city with temperature: {key}°C");
        }
        else
        {
            Console.WriteLine("Search results: ");
            Console.WriteLine(cities[index].ToString());
            loop= false;
        }
    }
    catch
    {
        Console.WriteLine("Only numbers, please.");
    }
} while (loop);
  • Python - binary search - list index out of range

    I'm learning Python programm (I'm totally beginner) and I have a little problem in my programm for binary search. This is my code:

    import random

def binary_search():
    numbers = []
    for x in range(1, 100):
        y = random.randint(1, 100)
        numbers.append(y)
        numbers.sort()

    start_index = numbers[0]
    end_index = numbers[-1]
    mid_index = numbers[(end_index+start_index)//2]

    user_choice = int(input("Is it your number: " + str(int(numbers[mid_index])) + "? \n0 - your number is lower,\n1 - it's your number,\n2 - your number is higher: "))
    times = 0

    while user_choice != 1:
        times += 1
        if user_choice == 0:
            end_index = mid_index-1
            numbers = numbers[start_index:end_index]
        elif user_choice == 2:
            start_index = mid_index+1
            numbers = numbers[start_index:end_index]

        mid_index = (end_index+start_index)//2
        user_choice = int(input("Is it your number: " + str(int(numbers[mid_index])) + "? \n0 - your number is lower,\n1 - it's your number,\n2 - your number is higher: "))

    print("Oh, that was hard... but it took only " + str(times) + " times to guess your number!")

    If the value of user_choice == 2, Python give me this:

    Traceback (most recent call last):
    File "C:\Users\Piotr\Desktop\IT\python\ćwiczenia\practice python\binary search v.2.py", line 38, in <module>
        binary_search()
    File "C:\Users\Piotr\Desktop\IT\python\ćwiczenia\practice python\binary search v.2.py", line 30, in binary_search
        user_choice = int(input("Is it your number: " + str(int(numbers[mid_index])) + "? \n0 - your number is lower,\n1 - it's your number,\n2 - your number is higher: "))
    IndexError: list index out of range

    I have no idea, why doesn't work, because for the value of user_choice == 0 or 1 works well. I can't see, where is wrong.

    (Maybe I'm just a stupid girl who doesn't understand how it works and how it should work well.)

    Thank you for helping me. Have a nice day and enjoy your coffee (or tea or whatever you drink) :)