Editing Binary search (section)

=== Running time and cache use ===
In analyzing the performance of binary search, another consideration is the time required to compare two elements. For integers and strings, the time required increases linearly as the encoding length (usually the number of [[bit]]s) of the elements increase. For example, comparing a pair of 64-bit unsigned integers would require comparing up to double the bits as comparing a pair of 32-bit unsigned integers. The worst case is achieved when the integers are equal. This can be significant when the encoding lengths of the elements are large, such as with large integer types or long strings, which makes comparing elements expensive. Furthermore, comparing [[Floating-point arithmetic|floating-point]] values (the most common digital representation of [[real number]]s) is often more expensive than comparing integers or short strings.

On most computer architectures, the [[Central processing unit|processor]] has a hardware [[Cache (computing)|cache]] separate from [[Random-access memory|RAM]]. Since they are located within the processor itself, caches are much faster to access but usually store much less data than RAM. Therefore, most processors store memory locations that have been accessed recently, along with memory locations close to it. For example, when an array element is accessed, the element itself may be stored along with the elements that are stored close to it in RAM, making it faster to sequentially access array elements that are close in index to each other ([[locality of reference]]). On a sorted array, binary search can jump to distant memory locations if the array is large, unlike algorithms (such as [[linear search]] and [[linear probing]] in [[hash tables]]) which access elements in sequence. This adds slightly to the running time of binary search for large arrays on most systems.<ref>{{cite journal|last1=Khuong|first1=Paul-Virak|last2=Morin|first2=Pat|s2cid=23752485|author2-link= Pat Morin |title=Array Layouts for Comparison-Based Searching|journal=Journal of Experimental Algorithmics|year=2017|volume=22|at=Article 1.3|doi=10.1145/3053370|arxiv=1509.05053}}</ref>