Binary Search in Array

Question

How would I implement a binary search using just an array?

Solution 1

Ensure that your array is sorted since this is the crux of a binary search.

Any indexed/random-access data structure can be binary searched. So when you say using "just an array", I would say arrays are the most basic/common data structure that a binary search is employed on.

You can do it recursively (easiest) or iteratively. Time complexity of a binary search is O(log N) which is considerably faster than a linear search of checking each element at O(N). Here are some examples from Wikipedia: Binary Search Algorithm:

Recursive:

BinarySearch(A[0..N-1], value, low, high) {  
    if (high < low)  
        return -1 // not found  
    mid = low + ((high - low) / 2) 
    if (A[mid] > value)  
        return BinarySearch(A, value, low, mid-1)  
    else if (A[mid] < value)  
        return BinarySearch(A, value, mid+1, high)  
    else
       return mid // found
    }

Iterative:

  BinarySearch(A[0..N-1], value) {
   low = 0
   high = N - 1
   while (low <= high) {
       mid = low + ((high - low) / 2)
       if (A[mid] > value)
           high = mid - 1
       else if (A[mid] < value)
           low = mid + 1
       else
           return mid // found
   }
   return -1 // not found
}

Solution 2

Binary Search in Javascript (ES6)

(If anyone needs)

Bottom-up:

function binarySearch (arr, val) {
    let start = 0;
    let end = arr.length - 1;
    let mid;

    while (start <= end) {
        mid = Math.floor((start + end) / 2);

        if (arr[mid] === val) {
            return mid;
        }
        if (val < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

Recursion:

function binarySearch(arr, val, start = 0, end = arr.length - 1) {
    const mid = Math.floor((start + end) / 2);

    if (val === arr[mid]) {
        return mid;
    }
    if (start >= end) {
        return -1;
    }
    return val < arr[mid]
        ? binarySearch(arr, val, start, mid - 1)
        : binarySearch(arr, val, mid + 1, end);
}

Comments

[Damarawy]

Remember to watch for overflow when calculating mid. (see googleresearch.blogspot.com/2006/06/… )

[Dennis Kioko]

@Firas Assad, Thanks, updated code to show the fix associated with preventing the overflow

[Jed]

It's one if statement if that is a requirement.

[Niklas R]

mid = low + ((high - low) / 2) is the same as mid = (low + high) / 2. Not sure with integer division in play, but the algorithm works nevertheless with both formulas.

[jarno]

You should check a[n], too, in the end. Otherwise does not find e.g. 1 from {0,1}.

[jarno]

@NiklasR Except when low+high produces integer overflow.

[Jed]

@jarno As conventional with C, n is the length of the (0-based) array so a[n] is not valid. Meanwhile, bsearch_double((double[]){0,1}, 2, 1) is valid and returns 1.

[AlphaGoku]

Wouldnt mid = (high - low) / 2 be OK?

[habib]

@AlphaGoku no it's not ok. Suppose there is no mid point in array then there will be two mid points and we have to choose the lower mid. So you should always have to choose that formula int mid = low + ((high - low)/2); to calculate lower mid because it's more reliable. Reference hackernoon.com/binary-search-in-detail-914944a1434a

[qulinxao]

s/int mid=low+high/2;/int mid=(low+high)/2;/ s/return binSearch(arr,low,high-1, num);/return binSearch(arr,low,mid-1, num);/ s/return binSearch(arr,low+1,high, num);/return binSearch(arr,mid+1,high, num);/

[Jeremy Caney]

Thank you for contributing an answer. Would you kindly edit your answer to to include an explanation of your code? That will help future readers better understand what is going on, and especially those members of the community who are new to the language and struggling to understand the concepts.