When the list is sorted we can use the binary search (also known as half-interval search, logarithmic search, or binary chop) technique to find items on the list. Here's a step-by-step description of using binary search:

1. Let min = 1 and max = n .
2. Guess the average of max and min rounded down so that it is an integer.
3. If you guessed the number, stop. You found it!
4. If the guess was too low, set min to be one larger than the guess.
5. If the guess was too high, set max to be one smaller than the guess.
6. Go back to step two. In this example we looking for array item with value 4 : When you do one operation in binary search we reduce the size of the problem by half (look at the picture below how do we reduce the size of the problem area) hence the complexity of binary search is

O(
log n) . The binary

search algorithm can be written either recursively or iteratively.

Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n) Implementation: JS

var binarySearch = function(array, value) {
  var guess,
  min = 0,
  max = array.length - 1;
  while(min <= max){
    guess = Math.floor((min + max) /2);
    if(array[guess] === value)
    return guess;
    else if(array[guess] < value)
    min = guess + 1;
    else
    max = guess - 1;
  }
return -1;
}

Java
// binary search example in Java
/* here Arr is an of integer type, n is size of array

and target is element to be found */ int binarySearch(int Arr[], int n, int target) {//set stating and ending index

int start = 0, ending = n-1;
while(start <= ending) {
  // take mid of the list
  int mid = (start + end) / 2;
  // we found a match
  if(Arr[mid] == target) {
    return mid;
  }
// go on right side
else if(Arr[mid] < target) {
  start = mid + 1;
}
// go on left side
else {
  end = mid - 1;
}
}
// element is not present in list
return -1;
}
PY
def BinarySearch(lys, val):
first = 0
last = len(lys)-1
index = -1
while (first <= last) and (index == -1):
mid = (first+last)//2
if lys[mid] == val:
index = mid
else:
if val<lys[mid]:
last = mid -1
else:
first = mid +1

return index

Linear (sequential) search goes through all possible elements in some array and compare each one with the

desired element. It may take up to

O(
n) operations, where N is the size of an array and is widely considered to

be horribly slow. In linear search when you perform one operation you reduce the size of the problem by one

(when you do one operation in binary search you reduce the size of the problem by half). Despite it, it can still be used when: You need to perform this search only once, You are forbidden to rearrange the elements and you do not have any extra memory, The array is tiny, such as ten elements or less, or the performance is not an issue at all, Even though in theory other search algorithms may be faster than linear search (for instance binary search), in practice even on medium-sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches, When the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only

O(
1)

You have no idea what you are searching. When you ask MySQL something like SELECT x FROM y WHERE z = t , and z is a column without an index, linear search is performed with all the consequences of it. This is why adding an index to searchable columns is important. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of (n+1)/2 comparisons, but the average case can be affected if the search probabilities for each element vary. When the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only

O(
1)
Implementation:
JS
function linearSearch(array, toFind){
  for(let i = 0; i < array.length; i++){
    if(array[i] === toFind) return i;
  }
return -1;
}
PY
# can be simply done using 'in' operator
if x in arr:
print arr.index(x)# If you want to implement Linear Search in Python
def search(arr, x):
for i in range(len(arr)):
if arr[i] == x:

return i return -1

When you do one operation in binary search we reduce the size of the problem by half. To answer the questions we have to answer, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2x
multiply by 2x:
2x = N

now do the log2:

log2(2x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N

this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element. The same concept explained graphically:

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.

1. Most used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0] .
2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0 . This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

When you do one operation in binary search we reduce the size of the problem by half. To answer the questions we have to answer, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2x
multiply by 2x:
2x = N

now do the log2:

log2(2x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N

this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element. The same concept explained graphically:

Problem

Consider: bool recur_search(int key, int values[], int lower, int upper)

{
  // base case 1: not in haystack
  if (upper < lower)
  {
    return false;
  }
int mid = (lower + upper) / 2;// base case 2: found
if (key == values[mid])
{
  return true;
}// recursive cases
else if (key < values[mid])
{
  recur_search(key, values, lower, mid - 1);
}
else
// (key > values[mid])
{
  recur_search(key, values, mid + 1, upper);
}// to get rid of "error: control may reach end of non-void function"
return false;
}

What's wrong with this code?

Solution

Classic mistake! Even though it is calling itself correctly, it is missing the code necessary to recursively return the result. As it is written above, it will execute the recursive call to itself, but when it does find a number, it will return true on the first step back through the recursion. However, at the second step and thereafter, the code will return to the calling recursion and process the next line of code because it has no instruction to do something else. It will drop through the if(upper < lower) block and hit the return false statement. So, from there on, it will just return false back up the recursion. The addition of one keyword, return , in two places, fixes the code:

// recursive cases
...
else if (key < values[mid])
{
  return recur_search(key, values, lower, mid - 1);
}
else
// (key > values[mid])
{
  return recur_search(key, values, mid + 1, upper);
}
...

Binary search requires the input data to be

sorted; linear search doesn't
Binary search requires an
ordering comparison (like > , < ); linear search only requires
equality comparisons
( = )
Binary search has complexity
O(
log n) ; linear search has complexity
O(
n)

Binary search requires
random access to the data; linear search only requires
sequential access
this can be very important - it means a

linear search can stream data of arbitrary size

**Jump Search **(also referred to as Block Search) is an algorithm used to search for the position of a target
element on a
sorted data collection or structure.

The fundamental idea behind this searching technique is to search fewer number of elements compared to linear search algorithm (which scans every element in the array to check if it matches with the element being searched or not). This can be done by skipping some fixed number of array elements or jumping ahead by fixed number of steps in every iteration. Lets consider a sorted array A[] of size n , with indexing ranging between 0 and n-1, and element x that needs to be searched in the array A[] . For implementing this algorithm, a block of size m is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows: Iteration 1: if ( x==A[0] ), then success, else, if ( x > A[0] ), then jump to the next block. Iteration 2: if ( x==A[m] ), then success, else, if ( x > A[m] ), then jump to the next block. Iteration 3: if ( x==A[2m] ), then success, else, if ( x > A[2m] ), then jump to the next block. At any point in time, if ( x < A[km] ), then a linear search is performed from index A[(k-1)m] to A[km] Consider the following inputs:

A[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}
item = 77

The single most important advantage of jump search when compared to binary search is that it does not rely on the division operator ( / ). Jump Search is highly efficient for searching arrays especially when its only-seeks-forward behavior is favorable - its average performance makes it sit somewhere between Binary Search with its

O(
log n)

complexity and Linear Search with an

O(
n) complexity.
Complexity Analysis:
Time Complexity: O(sqrt n) Space Complexity: O(sqrt n)

Jump Search would consecutively jump to its very last block searching for the target element, in turn causing an n/m number of jumps. Additionally, if the last element’s value of this block was greater than the target element, Jump Search would perform a linear search with m-1 iterations. This causes Jump Search to make (n/m) jumps with additional m-1 iterations. This value is minimum at m = √n . Therefore, the optimum block size is √n . Accordingly, Jump Search maintains a worst and average case efficiency of O(√n) complexity. The space complexity of this algorithm is

O(
1) since it does not require any additional temporary variables

or data structures for its implementation. Implementation: JS

function jumpSearch(arrayToSearch, valueToSearch){
  var length = arrayToSearch.length;
  var step = Math.floor(Math.sqrt(length));
  var index = Math.min(step, length)-1;
  var lowerBound = 0;
  while (arrayToSearch[Math.min(step, length)-1] < valueToSearch)
  {
    lowerBound = step;
    step += step;
    if (lowerBound >= length){
      return -1;
    }
}
var upperBound = Math.min(step, length);
while (arrayToSearch[lowerBound] < valueToSearch)
{
  lowerBound++;
  if (lowerBound == upperBound){
    return -1;
  }
}
if (arrayToSearch[lowerBound] == valueToSearch){
  return lowerBound;
}
return -1;
}

Java
package Searches;
public class JumpSearch implements SearchAlgorithm {
  public static void main(String[] args) {
    JumpSearch jumpSearch = new JumpSearch();
    Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (int i = 0; i < array.length; i++) {
      assert jumpSearch.find(array, i) == i;
    }
  assert jumpSearch.find(array, -1) == -1;
  assert jumpSearch.find(array, 11) == -1;
}/**
* Jump Search algorithm implements
*
* @param array the array contains elements
* @param key to be searched
* @return index of {@code key} if found, otherwise <tt>-1</tt>
*/
@Override
public <T extends Comparable<T>> int find(T[] array, T key) {
  int length = array.length;
  /* length of array */
  int blockSize = (int) Math.sqrt(length);
  /* block size to be jumped */
  int limit = blockSize;
  while (key.compareTo(array[limit]) > 0 && limit < array.length - 1) {
    limit = Math.min(limit + blockSize, array.length - 1);
  }
for (int i = limit - blockSize; i <= limit; i++) {
  if (array[i] == key) {
    /* execute linear search */
    return i;
  }
}
return -1;
/* not found */
}
}
PY
import math
def jump_search(arr,search):
low = 0
interval = int(math.sqrt(len(arr)))
for i in range(0,len(arr),interval):
if arr[i] < search:
low = i
elif arr[i] == search:

return i else: break

bigger number is found

c=low
for j in arr[low:]:
if j==search:

return c

c+=1

return "Not found" arr = [ i for i in range(1,200,15)]

res = jump_search(arr, 196)
print(res)
# prints 13

The first difference is that the while loop from iterative approach is replaced by a recursive call back to the same method with the new values of low and high passed to the next recursive invocation along with Array and key or target element. The second difference is that instead of returning false when the while loop exits in the iterative version, in case of the recursive version, the condition of low > high is checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning false. Also, note that the recursive invocations of binarySearch() return back the search result up the recursive call stack so that true or false return value is passed back up the call stack without any further processing. To further optimize the solution, in term of running time, we could consider implement the tail-recursive solution, where the stack trace of the algorithm would not pile up, which leads to a less memory footprint during the running time. To have the tail-recursive solution, the trick is to simply return the result from the next recursive function instead of further processing. Implementation: JS

function binarySearch(sortedArray, searchValue, minIndex, maxIndex) {
  var currentIndex;
  var currentElement;
  while (minIndex <= maxIndex) {
    // Find the value of the middle of the array
    var middleIndex = (minIndex + maxIndex) / 2 | 0;
    currentElement = sortedArray[middleIndex];
    // It's the same as the value in the middle - we can return!
    if (currentElement === searchValue)
    {
      return middleIndex;
    }
  // Is the value less than the value in the middle of the array
  if (currentElement < searchValue) {
    return binarySearch(sortedArray, searchValue, middleIndex + 1, maxIndex);
  }
// Is the value greater than the value in the middle of the array
if (currentElement > searchValue) {
  return binarySearch(sortedArray, searchValue, minIndex, middleIndex - 1);
}
}
return -1;
}
Java
// Find out if a key x exists in the sorted array
// A[low..high] or not using binary search algorithm
public static int binarySearch(int[] A, int low, int high, int x) {
  // Base condition (search space is exhausted)
  if (low > high) {
    return -1;
  }// we find the mid value in the search space and

// compares it with key value
int mid = (low + high) / 2;// overflow can happen. Use beleft
// int mid = low + (high - low) / 2;
// Base condition (key value is found)
if (x == A[mid]) {
  return mid;
}// discard all elements in the right search space
// including the mid element
else if (x < A[mid]) {
  return binarySearch(A, low, mid - 1, x);
}// discard all elements in the left search space
// including the mid element
else {
  return binarySearch(A, mid + 1, high, x);
}
}
PY
class Solution:
def searchInsert(self, nums, target):
return self.tail_recursive_searchInsert(0, nums, target)
def tail_recursive_searchInsert(self, start, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int

return the position to insert a new element into the sorted list. Note: the solution can be implemented in a recursive way. """

size = len(nums)
if (size == 0):
# empty input list, early exit

return start

mid_index = int(size/2)
if (nums[mid_index] == target):

return start + mid_index

elif (nums[mid_index] > target):
return self.tail_recursive_searchInsert(
start, nums[0:mid_index], target)
else:
return self.tail_recursive_searchInsert(
start+mid_index+1, nums[mid_index+1:], target)

Interpolation Search is an algorithm similar to Binary Search for searching for a given target value in a sorted array. It is an improvement over Binary Search for instances, where the values in a sorted array areuniformly distributed.

The binary search always chooses the middle of the remaining search space. On a contrast Interpolation search, at each search step, calculates (using interpolation formula) where in the remaining search space the targetmight be present, based on the low and high values of the search space and the value of the target. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side. The value actually found at this estimated position is then compared to the target value. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. The idea of the** interpolation formula** or partitioning logic is to return higher value of pos when element to be searched is closer to arr[hi] . And smaller value when closer to arr[low].

arr[] ==> Array where elements need to be searched
x ==> Element to be searched
low ==> Starting index in arr[]
hi ==> Ending index in arr[]
pos = low + [ (x-arr[low])*(hi-low) / (arr[hi]-arr[Low]) ]
Complexity Analysis:
Time Complexity: O(log log n) Space Complexity: O(log log n)

In the interpolation search algorithm, the midpoint is computed in such a way that it gives a higher probability of obtaining our search term faster. The worst case complexity of interpolation search is

O(
n) . However, its
average case complexity, under the assumption that the keys are uniformly distributed, is _ O(log log N) .

It can be proven that Interpolation Search repeatedly reducing the problem to a subproblem of size that is the square root of the original problem size, and algorithm will terminate after

O(log log n) steps (see proof
here). When the values are equally dispersed into the interval this search algorithm can be extremely useful –
way faster than the binary search (that divides searching space
by half).
Implementation:
JS
const interpolationSearch = (array, key) => {// if array is empty.
  if (!array.length) {

    return -1;
  }
let low = 0;
let high = array.length - 1;
while (low <= high && key >= array[low] && x <= array[high]) {// calculate position with
  let pos = low + Math.floor(((high - low) * (key - array[low])) / (array[high] - array[low]));// if all elements are same then we'll have divide by 0 or 0/0
  // which may cause NaN
  pos = Number.isNaN(pos) ? low : pos;
  if (array[pos] === key) {
    return pos;
  }
if (array[pos] > key) {
  high = pos - 1;
} else {
  low = pos + 1;
}
}// not found.
return -1;
};
PY
def InterpolationSearch(data, key):
left = 0
right = len(data) - 1
while left < right:
idx = int( (right - left) * (key - data[left]) / (data[right] - data[left]) ) + left
if data[idx] is key:

return idx elif data[idx] < key:

left = idx + 1
else:
right = idx - 1

return -1

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.

1. Most used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0] .
2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0 . This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

With regard to time complexity, recursive and iterative methods both will give you

O(
log n) time

complexity, with regard to input size, provided you implement correct binary search logic. Focusing on space complexity: The iterative approach is more efficient since we are allocating a constant amount O(1) of space for the function call and constant space for variable allocations. There have been concerns around the recursive version regarding the function stack it is going to use. However, once you see it carefully, the recursive version is a tail recursion. Most of the modern compiler converts the tail recursion into iterative program. Thus, there won't be any issue regarding the usage of the function stack. P.S. A tail recursion is also a kind of recursion but it will make the return value of the recursion call as the last statement of the method. This will make the calculation occurs before the recursion call and hence there is no need to keep the stack to store the intermediate value when it moves to the next recursive call.

The idea behind linear search is to compare the search item with the elements in the list one by one (using a loop) and stop as soon as we get the first copy of the search element in the list. Now considering the worst case in which the search element does not exist in the list of size N then the Simple Linear Search will take a total

of 2N+1 comparisons ( N comparisons against every element in the search list and N+1 comparisons to test against the end of the loop condition).

for (int i = 0; i < length; i++) {
  // N+1 comparisons
  if (array[i] == elementToSearch) {
    // N comparisons
    return i;
    // I found the position of the element requested
  }
}

The idea of Sentinel Linear Search is to reduce the number of comparisons required to find an element in a list. Here we replace the last element of the list with the search element itself and run a while loop to see if there exists any copy of the search element in the list and quit the loop as soon as we find the search element. This will reduce one comparison in each iteration.

while(a[i] != element)
// N+2 comparisons worst case
i++;

In that case the while loop makes only one comparison in each iteration and it is sure that it will terminate since the last element of the list is the search element itself. So in the worst case ( if the search element does not exists in the list ) then there will be at most N+2 comparisons ( N comparisons in the while loop and 2 comparisons in the if condition). Which is better than ( 2N+1 ) comparisons as found in Simple Linear Search. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Take note that both the algorithms (Simple Linear and Sentinel) have time complexity of

O(
n) .
Implementation:
CS
/// <summary>
/// Gets the index of first founded item
/// </summary>
/// <typeparam name="T">The type of array</typeparam>
/// <param name="array">Input array</param>
/// <param name="value">Value of searching item</param>
/// <param name="equalityComparer">Custom comparer</param>
/// <returns>The index of founded item or -1 if not found</returns>
public static int BetterLinearSearch < T > (this IEnumerable < T > array, T value, IEqualityComparer < T
> equalityComparer = null) {
  if (equalityComparer == null) equalityComparer = new DefaultEqualityComparer < T > ();
  int arrayLength = array.Count();
  T lastItem = array.Last();
  array = array.SetElement(arrayLength - 1, value);
  int index = 0;
  while (!equalityComparer.Equals(array.ElementAt(index), value))
  index++;
  if (index < arrayLength - 1) return index;
  if (equalityComparer.Equals(lastItem, value)) return arrayLength - 1;
  return - 1;
}

PY
def sentinelSearch(ar,n,l):
# ar : array
# n : item to be searched
# l : size of array
last = ar[l-1]
# saving last element in other variable
ar[l-1] = n
# assigning last element as required
i = 0
while ar[i]!=n:
i+=1
ar[l-1] = last
if (i<l-1) or n==ar[l-1]:
print('Item found at',i)
else:
print('Item not Found')

Binary Search has a better time complexity (

O(
log n) ) than Jump Search (
O(√n) ), but Jump Search has an
advantage that we traverse back only once (Binary Search may require up to
O(
log n) backward jumps;

consider a situation where the element to be searched is the smallest element or smaller than the smallest). So in a system where binary search is costly a backward traversal is more costly than a forward traversal, we might want to use Jump Search. For examples where traversing backward could be more expensive, think of data that is stored on tapes: when traversing in forward direction, the tape can just keep winding on-and-on while providing data, but with a backward traversal, the tape needs to stop winding forward (this costs time), perform a rewind, and then reverse its direction again (again, this costs extra time). Or take disk drives, where the disk has to go through one complete revolution to arrive at the spot for reading a previous block.

In traditional linear search, there are n comparison for comparing with the required number and n+1 for looping condition, sums up to make 2n+1 comparisons. But, if we replace the last element of the list with the search element itself and run a while loop to see if there exists any copy of the search element, we can get our answer in n+2 comparisons at max. Note that both the algorithms have time complexity of O(n) .

def sentinelSearch(ar,n,l):

# ar : array
# n : item to be searched
# l : size of array
last = ar[l-1]
# saving last element in other variable
ar[l-1] = n
# assigning last element as required
i = 0
while ar[i]!=n:
i+=1
ar[l-1] = last
if (i<l-1) or n==ar[l-1]:
print('Item found at',i)
else:
print('Item not Found')

When considering Sentinel Search note:

1. It's not always possible to have a sentinel. For example modifying a shared array in a multithreaded context this way not safe. Or the array might be actually read-only for some reason.
2. Compiler optimizations. Lots of time the loop over array gets unrolled and you actually do less than n comparisons for looping condition.
3. Algorithm has to mutate the array (usually not good) and you have to keep special value for sentinel (not always possible).
4. Will you ever notice any speed increase from this? No
5. Will you notice a lack of readability? Yes
6. Will you notice an unnecessary array mutation that might cause concurrency issues? Yes So answering the question, the real benefit of the sentinel optimization would be really negligible and premature optimization is the root of all evil.

Binary Search has a better time complexity (

O(
log n) ) than Jump Search (
O(√n) ), but Jump Search has an
advantage that we traverse back only once (Binary Search may require up to
O(
log n) backward jumps;

consider a situation where the element to be searched is the smallest element or smaller than the smallest). So in a system where binary search is costly a backward traversal is more costly than a forward traversal, we might want to use Jump Search.

For examples where traversing backward could be more expensive, think of data that is stored on tapes: when traversing in forward direction, the tape can just keep winding on-and-on while providing data, but with a backward traversal, the tape needs to stop winding forward (this costs time), perform a rewind, and then reverse its direction again (again, this costs extra time). Or take disk drives, where the disk has to go through one complete revolution to arrive at the spot for reading a previous block.

In traditional linear search, there are n comparison for comparing with the required number and n+1 for looping condition, sums up to make 2n+1 comparisons. But, if we replace the last element of the list with the search element itself and run a while loop to see if there exists any copy of the search element, we can get our answer in n+2 comparisons at max. Note that both the algorithms have time complexity of O(n) . def sentinelSearch(ar,n,l):

# ar : array
# n : item to be searched
# l : size of array
last = ar[l-1]
# saving last element in other variable
ar[l-1] = n
# assigning last element as required
i = 0
while ar[i]!=n:
i+=1
ar[l-1] = last
if (i<l-1) or n==ar[l-1]:
print('Item found at',i)
else:
print('Item not Found')

When considering Sentinel Search note:

1. It's not always possible to have a sentinel. For example modifying a shared array in a multithreaded context this way not safe. Or the array might be actually read-only for some reason.
2. Compiler optimizations. Lots of time the loop over array gets unrolled and you actually do less than n comparisons for looping condition.
3. Algorithm has to mutate the array (usually not good) and you have to keep special value for sentinel (not always possible).
4. Will you ever notice any speed increase from this? No
5. Will you notice a lack of readability? Yes
6. Will you notice an unnecessary array mutation that might cause concurrency issues? Yes So answering the question, the real benefit of the sentinel optimization would be really negligible and premature optimization is the root of all evil.

Problem

I've heard that it's possible to implement binary search over a doubly-linked list in

O(
n) time. Accessing a
random element of a doubly-linked list takes
O(
n) time, and binary search accesses
O(
log n) different
elements, so shouldn't the runtime be
O(
log n) ) instead?

### Solution

It's technically correct to say that the runtime of binary search on a doubly-linked list is

O(
log n) ), but that's not

a tight upper bound. Using a slightly better implementation of binary search and a more clever analysis, it's possible to get binary search to run in time

O(
n) .

The basic idea behind binary search is the following: If the list is empty, the element being searched for doesn't exist. Otherwise: Look at the middle element. If it matches the element in question, return it. If it's bigger than the element in question, discard the back half of the list. If it's smaller than the element in question, discard the front half of the list. A naive implementation of binary search on a doubly-linked list would work by computing the indices to look up on each iteration (just like in the array case), then access each one by starting at the front of the list and scanning forward the appropriate number of steps. This is indeed very slow. We can speed this up by a factor of Θ(log n) by being more clever with our approach. The reason the previous algorithm is slow is that every time we need to look up an element, we start the search from the beginning of the

array. However, we don't need to do this. After looking up the middle element the first time, we're already in the middle of the array, and we know that the next lookup we're going to make will be either at position n / 4 or 3n / 4, which is only distance n / 4 from where we left off (compared to n / 4 or 3n / 4 if we start from the beginning of the array). What if we just trekked out from our stopping position (n / 2) to the next position, rather than restarting at the front of the list? Here's our new algorithm. Begin by scanning to the middle of the array, which requires n / 2 steps. Then, determine whether to visit the element at the middle of the first half of the array or the middle of the second half of the array. Reaching there from position n / 2 only requires n / 4 total steps. From there, going to the midpoint of the quarter of the array containing the element takes only n / 8 steps, and going from there to the midpoint of the eighth of the array containing the element takes only n / 16 steps, etc. This means that the total number of steps made is given by n / 2 + n / 4 + n / 8 + n / 16 + ...

= n (1/2 + 1/4 + 1/8 + ...)
≤ n

This follows from the fact that the sum of the infinite geometric series 1/2 + 1/4 + 1/8 + ... is 1. Therefore, the total work done in the worst case only Θ(n) , which is much better than the Θ(n log n) worst case from before.

Like linear search and binary search, ternary search is a searching technique that is used to determine the position of a specific value in an array. In binary search, the sorted array is divided into two parts while in ternary search, it is divided into 3 parts and then you determine in which part the element exists. Ternary search, like binary search, is a divide-and-conquer algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before you begin the search. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list. Ternary search has a lesser number of iterations than Binary Search but Ternary search also leads to morecomparisons. Average number of comparisons:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Worst number of comparisons:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
Implementation:
CS

int ternary_search(int l,int r, int x)
{
  if(r>=l)
  {
    int mid1 = l + (r-l)/3;
    int mid2 = r - (r-l)/3;
    if(ar[mid1] == x)
    return mid1;
    if(ar[mid2] == x)
    return mid2;
    if(x<ar[mid1])
    return ternary_search(l,mid1-1,x);
    else if(x>ar[mid2])
    return ternary_search(mid2+1,r,x);
    else
    return ternary_search(mid1+1,mid2-1,x);
  }
return -1;
}
Java
public static int ternarySearch(int[] A, int x)
{
  int left = 0, right = A.length\ - 1;
  while (left <= right)
  {
    int leftMid = left + (right - left) / 3;
    int rightMid = right - (right - left) / 3;
    // int leftMid = (2*left + right) / 3;
    // int rightMid = (left + 2*right) / 3;
    if (A[leftMid] == x) {
      return leftMid;
    } else if (A[rightMid] == x) {
      return rightMid;
    } else if (A[leftMid] > x) {
      right = leftMid - 1;
    } else if (A[rightMid] < x) {
      left = rightMid + 1;
    } else {
      left = leftMid + 1;
      right = rightMid - 1;
    }
}
return -1;
}

Like linear search and binary search, ternary search is a searching technique that is used to determine the position of a specific value in an array. In binary search, the sorted array is divided into two parts while in ternary search, it is divided into 3 parts and then you determine in which part the element exists. Ternary search, like binary search, is a divide-and-conquer algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before you begin the search. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list. Ternary search has a lesser number of iterations than Binary Search but Ternary search also leads to morecomparisons. Average number of comparisons:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Worst number of comparisons:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
Implementation:
CS
int ternary_search(int l,int r, int x)
{
  if(r>=l)
  {
    int mid1 = l + (r-l)/3;
    int mid2 = r - (r-l)/3;
    if(ar[mid1] == x)
    return mid1;
    if(ar[mid2] == x)
    return mid2;
    if(x<ar[mid1])
    return ternary_search(l,mid1-1,x);
    else if(x>ar[mid2])
    return ternary_search(mid2+1,r,x);
    else
    return ternary_search(mid1+1,mid2-1,x);
  }
return -1;
}
Java
public static int ternarySearch(int[] A, int x)
{
  int left = 0, right = A.length\ - 1;
  while (left <= right)
  {
    int leftMid = left + (right - left) / 3;
    int rightMid = right - (right - left) / 3;
    // int leftMid = (2*left + right) / 3;
    // int rightMid = (left + 2*right) / 3;
    if (A[leftMid] == x) {
      return leftMid;
    } else if (A[rightMid] == x) {
      return rightMid;
    } else if (A[leftMid] > x) {
      right = leftMid - 1;
    } else if (A[rightMid] < x) {
      left = rightMid + 1;
    } else {
      left = leftMid + 1;
      right = rightMid - 1;
    }
}
return -1;
}

Rounding up works too. Long Answer: What is important is the number of elements to either side of the guess. If the number of elements remaining are odd then we will have (n-1)/2 element above and below our guess. No rounding is required. If the number of elements remaining are even then we will have n/2 elements on one side of the guess and n/2-1 elements on the other side, regardless of whether we round up or down. (the rounding determines whether the smaller chunk will be above or below the guess) After we look at the value of our guess we will be able to eliminate the elements above or below our guess. The number of guesses required to find a particular element will be different depending on whether we round up or round down. However, if we performed a series of binary searches to find every element, one by one,and took the grand total of the number of guesses from all of these searches, the grand total would be the same regardless of whether we round up or down. This means that the average number of guesses to find an element is the same, regardless of whether we round up or round down.

Fibonacci search is a search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in

O(
log n) time complexity.

Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two unequal parts that have sizes that are consecutive Fibonacci numbers. Some facts to note: Fibonacci search has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift, division or multiplication, operations that were less common at the time Fibonacci search was first published Binary search works by dividing the seek area in equal parts 1:1 . Fibonacci search can divide it into parts approaching 1:1.618 while using the simpler operations.

On average, Fibonacci search requires 4% more comparisons than binary search Fibonacci Search examines relatively closer elements in subsequent steps. So when input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful. Thus Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a non-uniform access memory storage. Let the length of given array be length and the element to be searched be key . Steps of Fibonacci Search:

1. Find the smallest Fibonacci number F(n) that F(n) - 1 >= length

2. F(n) = F(n-1) + F(n-2) => F(n) - 1 = [ F(n-1) - 1 ] + (1) + [ F(n-2) - 1 ] , where (1) here is for the
middle item (the m in below figure).
// |<--------- p: F(n) - 1 --------->|
// |<--- q: F(n-1) - 1 --->| |<-- r: F(n-2) - 1 -->|
// +----+---+--------------------+---+---+---+---+
// | | k | | m | | k | |
// +----+---+--------------------+---+---+---+---+
// ^
3. If key < m , then search key in q = F(n-1) - 1 :
// |<--- p: F(n-1) - 1 --->|
// |<----- q ----->| |<-- r -->|
// +----+---+------+---+---------+
// | | k | | m | |
// +----+---+------+---+---------+
for that set p = F(n-1) - 1, q = F(n-2) - 1, r = F(n-3) - 1 and repeat the process. Here Fibonacci numbers
go

backward once. These indicate elimination of approximately one-third of the remaining array. 4. If key > m , then repeat then search key in r = F(n-2) - 1 :

// |<-- p: F(n-2) - 1 -->|
// |<--- q --->| |<- r ->|
// +---+---+---+
// | | k | | m
// +---+---+---+
// ^
For that, set p = F(n-2) - 1, q = F(n-3) - 1, r = F(n-4) - 1 and repeat the process. Here Fibonacci
numbers go

backward twice, indicating elimination of approximately two-third of the remaining array. Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n) Fibonacci search has an average- and worst-case complexity of

O(
log n) . The worst case will occur when we
have our target in the larger (2/3) fraction of the array, as we proceed to find it. In other words, we are
eliminating the smaller (1/3) fraction of the array every time. We call once for n, then for (2/3) n, then for (4/9) n

and henceforth.

Implementation: CS #include #include #include "search.h" typedef struct FibonacciValues

{
  // Fibonacci number: F(n) = F(n-1) + F(n-2)
  int Fn_2; // F(n-2)
  int Fn_1; // F(n-1)
  int Fn; // F(n)
  FibonacciValues(int fn_2, int fn_1, int fn)
  : Fn_2(fn_2)
  , Fn_1(fn_1)
  , Fn(fn)
  {
    assert(Fn == Fn_1 + Fn_2);
  }
~FibonacciValues()
{
}
void forward()
{
  Fn_2 = Fn_1;
  Fn_1 = Fn;
  Fn = Fn_1 + Fn_2;
  assert(Fn == Fn_1 + Fn_2);
}
void backward()
{
  Fn = Fn_1;
  Fn_1 = Fn_2;
  Fn_2 = Fn - Fn_1;
  assert(Fn == Fn_1 + Fn_2);
}
} FibonacciValues;
// Returns the smallest Fibonacci number that is greater than or equal to k.
FibonacciValues GetFibonacci(int k)
{
  FibonacciValues fib(0, 1, 1);
  while (fib.Fn < k) {
    fib.forward();
  }
return fib;
}
// Notice that the current middle might exceed the array!
int fibonacciSearch(int list[], const unsigned int length, int key)
{
  assert(list && length);

  int left = 0, right = length - 1, middle;
  // Find a fibonacci number F(n) that F(n) - 1 >= length
  FibonacciValues fib = GetFibonacci(length + 1);
  while (left <= right) {
    // Avoid the middle is over the array.
    middle = std::min(left + (fib.Fn_1 - 1), right);
    if (list[middle] == key) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
      fib.backward();
    } else { // list[middle] < key
    left = middle + 1;
    fib.backward(); fib.backward();
  }
}
return NOT_FOUND;
}
JS
function fib(n) {
  if (n <= 0)
  return 0;
  if (n <= 2)
  return 1;
  return fib(n-1) + fib(n-2);
}
function smallest_greater_eq_fib(n) {
  let f = fib(0),
  cu = 0;
  while (f < n)
  f = fib(++cu);
  return cu;
}
async function fibonacciSearch(a, k, l, r, display) {
  let f = smallest_greater_eq_fib(r-l+1);
  while (f >= 0) {
    i = Math.min(l+fib(f-1), r-1);
    i = Math.max(0, i);
    refresh(glob_comp, a[i]);
    display(a, i, l, r);
    await sleep(glob_sleep_time);
    if (a[i]==k) {
      glob_comp++;
      refresh(glob_comp, a[i]);
      return new Promise(resolve => resolve(i));
    } else if (k < a[l+fib(f-1)]) {
      glob_comp+=2;
      refresh(glob_comp, a[i]);
      r = i;
      f-=1;
    } else {
      glob_comp+=2;
      refresh(glob_comp, a[i]);
      l = i;
      f-=2;
    }

}
return new Promise(resolve => resolve(-1));
}
Java
public class Fibonacci_Search
{
  static int kk = -1, nn = -1;
  static int fib[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
    377, 610, 98, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
    75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
    3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
    102334155, 165580141 };
  static int fibsearch(int a[], int n, long x)
  {
    int inf = 0, pos, k;
    if (nn != n)
    {
      k = 0;
      while (fib[k] < n)
      k++;
      kk = k;
      nn = n;
    }
  else
  k = kk;
  while (k > 0)
  {
    pos = inf + fib[--k];
    if ((pos >= n) || (x < a[pos]))
    ;
    else if (x > a[pos])
    {
      inf = pos + 1;
      k--;
    }
  else
  return pos;
}
return -1;
}
}
PY
def FibonacciSearch(lys, val):
fibM_minus_2 = 0
fibM_minus_1 = 1
fibM = fibM_minus_1 + fibM_minus_2
while (fibM < len(lys)):
fibM_minus_2 = fibM_minus_1
fibM_minus_1 = fibM
fibM = fibM_minus_1 + fibM_minus_2
index = -1;
while (fibM > 1):
i = min(index + fibM_minus_2, (len(lys)-1))
if (lys[i] < val):
fibM = fibM_minus_1
fibM_minus_1 = fibM_minus_2
fibM_minus_2 = fibM - fibM_minus_1
index = i
elif (lys[i] > val):
fibM = fibM_minus_2

fibM_minus_1 = fibM_minus_1 - fibM_minus_2
fibM_minus_2 = fibM - fibM_minus_1
else :

return i

if(fibM_minus_1 and index < (len(lys)-1) and lys[index+1] == val):
return index+1;

return -1

Exponential Search (also called Doubling Search or Galloping Search or Struzik Search) is explicitly designed for sorted, unbounded lists (infinite arrays or arrays with unknown size) whereas binary search deals with bounded lists (size is known). It has two steps:

1. Search for a position of first element greater or equal than the target value. Assuming that the list is sorted in ascending order, the algorithm looks for the first exponent, j , where the value arr(2j) is greater than the search key (target value). If the element at the current index is smaller than the search key, the algorithm repeats, skipping to the next search index by doubling it, calculating the next power of 2.
2. Do the binary search from the beginning to the found end Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n) The first stage of the algorithm takes O(log i) time, where i is the index where the search key would be in the list. The second part of the algorithm also takes

O(log i) time. As the second stage is simply a binary search, it
takes
O(
log n) where n is the size of the interval being searched. This gives the algorithm a total runtime,

calculated by summing the runtimes of the two stages, of

O(log i) +_ O(log i) _ =
2 O(log i) =
O(log i) .
Implementation:
JS
function exponentialSearch(arrayToSearch, valueToSearch){
  if (arrayToSearch[0] == valueToSearch){
    return 0;
  }
var i = 1;
while (i < arrayToSearch.length && arrayToSearch[i] <= valueToSearch){
  i = i*2;
}
return binarySearch(arrayToSearch, valueToSearch);
}
PY

def exponential_search(arr, p):
i = 0
while (arr[2 ** i] < p):
i += 1
binary_search(arr, p, i)

Consider a sorted integer array of size n with a block size of m . Jump Search would consecutively jump to its very last block searching for the target element, in turn causing an n/m number of jumps. Additionally, if the last element’s value of this block was greater than the target element, Jump Search would perform a linear search with m-1 comparisons. This causes Jump Search to make (n/m) jumps with additional m-1 comparisons. Hence, the total number of comparisons will be (n/m+(m-1)) . This expression has to be minimum, so that we get the smallest value of m (block size). On differentiating this expression with respect to m and equating it with 0, we get:

n/-m2+1 = 0
n/m2 = 1
m = √n

Hence, the optimal jump size is √n, where n is the size of the array to be searched or the total number of elements to be searched.