Day n+5 of studying until I get a new job

Today, I am just going to learn random stuff but DSA.

1. Why start + (end — start)/2 is preferable method for calculating middle of an array?

• I observed this pattern in binary search where middle index was calculated using this formula instead of (start+end)/2
• The reason for using the expression mid = start + (end - start) / 2 instead of mid = (start + end) /2 when calculating the middle index in binary search or other similar algorithms is to prevent integer overflow.
• (start + end) / 2 fails for large values of start and end. Specifically, it fails if the sum of low and high is greater than the maximum positive value of int data type (i.e., 231–1). The sum overflows to a negative value, and the value stays negative when divided by two. This causes an array index out of bounds with unpredictable results.
• By using the expression mid = start + (end - start) / 2, you are calculating the middle index while avoiding the direct addition of start and end, which can help prevent integer overflow. The subtraction (end - start) makes sure that the difference is calculated before any addition is done (due to BODMAS rule), reducing the chance of overflow
• More faster way which works in Java: int mid = (start + end) >>> 1;

2. Why do arrays have fixed size?

• Arrays have a fixed size mainly because of how memory is allocated internally.

Simple Summary

Arrays are fixed in size because: 👉 They need continuous memory allocated upfront 👉 Resizing would break this and be expensive (O(n))

References:

https://leetcode.com/discuss/post/3880518/why-start-end-start2-is-preferable-metho-4bpq/

[embed]Bitwise Right Shift Operators in Java - GeeksforGeeks Your All-in-One Learning Portal: GeeksforGeeks is a comprehensive educational platform that empowers learners across…www.geeksforgeeks.org

[embed]How to calculate "mid" or Middle Element Index in Binary Search? - GeeksforGeeks Your All-in-One Learning Portal: GeeksforGeeks is a comprehensive educational platform that empowers learners across…www.geeksforgeeks.org