Binary Search in Array

Question

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

Answer 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
}

Answer 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);
}

Answer 3

The single comparison version is fast and concise

int bsearch_double(const double a[], int n, double v) {
  int low = 0, mid;
  while (n - low > 1) {
    mid = low + (n - low) / 2;
    if (v < a[mid]) n   = mid;
    else            low = mid;
  }
  return (low < n && a[low] == v) ? low : -1;
}

Answer 4

It depends if you have repetition of one element in your array or no and if you care about multiple findings or not. I have two methods in this implementation. One of them returns only first finding, but the other one returns all findings of the key.

import java.util.Arrays;

public class BinarySearchExample {

    //Find one occurrence
    public static int indexOf(int[] a, int key) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }

    //Find all occurrence
    public static void PrintIndicesForValue(int[] numbers, int target) {
        if (numbers == null)
            return;

        int low = 0, high = numbers.length - 1;
        // get the start index of target number
        int startIndex = -1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (numbers[mid] > target) {
                high = mid - 1;
            } else if (numbers[mid] == target) {
                startIndex = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }

        // get the end index of target number
        int endIndex = -1;
        low = 0;
        high = numbers.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (numbers[mid] > target) {
                high = mid - 1;
            } else if (numbers[mid] == target) {
                endIndex = mid;
                low = mid + 1;
            } else
                low = mid + 1;
        }

        if (startIndex != -1 && endIndex != -1){
            System.out.print("All: ");
            for(int i=0; i+startIndex<=endIndex;i++){
                if(i>0)
                    System.out.print(',');
                System.out.print(i+startIndex);
            }
        }
    }

    public static void main(String[] args) {

        // read the integers from a file
        int[] arr = {23,34,12,24,266,1,3,66,78,93,22,24,25,27};
        Boolean[] arrFlag = new Boolean[arr.length];
        Arrays.fill(arrFlag,false);

        // sort the array
        Arrays.sort(arr);

        //Search
        System.out.print("Array: ");
        for(int i=0; i<arr.length; i++)
            if(i != arr.length-1){
                System.out.print(arr[i]+",");
            }else{
                System.out.print(arr[i]);
            }

        System.out.println("\nOnly one: "+indexOf(arr,24));
        PrintIndicesForValue(arr,24);

    }

}

For more information, please visit https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/BinarySearchExample.java. I hope it helps.

Answer 5

Did implement below code in Java,simple and fast /** * Binary Search using Recursion * @author asharda * */ public class BinSearch {

  /**
   * Simplistic BInary Search using Recursion
   * @param arr
   * @param low
   * @param high
   * @param num
   * @return int
   */
  public int binSearch(int []arr,int low,int high,int num)
  {
    int mid=low+high/2;
    if(num >arr[high] || num <arr[low])
    {
      return -1;
    }

    while(low<high)
    {
      if(num==arr[mid])
      {
        return mid;

      }
      else  if(num<arr[mid])
      {
       return  binSearch(arr,low,high-1, num);
      }

      else  if(num>arr[mid])
      {
        return binSearch(arr,low+1,high, num);
      }

    }//end of while

    return -1;
  }

  public static void main(String args[])
  {
    int arr[]= {2,4,6,8,10};
    BinSearch s=new BinSearch();
    int n=s.binSearch(arr, 0, arr.length-1, 10);
    String result= n>1?"Number found at "+n:"Number not found";
    System.out.println(result);
  }
}

Answer 6

Here is simple solution in python programming language:

def bin(search, h, l):
    mid = (h+l)//2
    if m[mid] == search:
        return mid
    else:
        if l == h:
            return -1
        elif search > m[mid]:
            l = mid+1
            return bin(search, h, l)
        elif search < m[mid]:
            h = mid-1
            return bin(search, h, l)
    
m = [1,2,3,4,5,6,7,8]
tot = len(m)
print(bin(10, len(m)-1, 0))

Here is the process :

• get mid point
• if mid point == search return mid point
• else if higher and lower points are same then return -1
• if search value is greater than mid point then make mid point+1 as lower value
• if search value is less than mid point then make mid point-1 as higher value

Answer 7

short loop for binary search:

function search( nums, target){    
    for(let mid,look,p=[0,,nums.length-1]; p[0]<=p[2]; p[look+1]=mid-look){
        mid = (p[0] + p[2])>>>1
        look = Math.sign(nums[mid]-target)
        if(!look) 
            return mid
    }
    return -1
}

---

idea is replacing:

if(nums[mid]==target)
    return mid
else if(nums[mid]>target)
    right = mid - 1
else //here must nums[mid]<target
    left  = mid + 1

with more tacit(and possible less computation hungry) if observe former is equal:

switch(dir=Math.sign(nums[mid]-target)){
    case -1: left  = mid - dir;break;
    case  0: return  mid
    case  1: right = mid - dir;break;
}

so if left,mid,right vars situated sequentially we can address to all of them throw &mid[-1,0,1 respectively] in C pointer sense :

dir=Math.sign(nums[mid]-target)
&mid[dir] = mid - dir

now we get body of loop so we can construct binary search:

while(dir && left <= right){
    mid = (left + right)>>>2
    dir=Math.sign(nums[mid]-target)
    &mid[dir] = mid - dir
}

after while we just:

return [dir,mid]

with semantic that

for dir == -1 then nums[mid]<target<nums[mid+1] // if nums[mid+1 ] in start seaching domain
for dir ==  0 then mid is place of target in array 
for dir ==  1 then nums[mid-1]<target<nums[mid] // if nums[mid-1 ] in start seaching domain        

so in some more human pseudocode javascript function equivalent:

    function search( nums, target){
        let dir=!0,[left, mid, right]=[0, , nums.length-1]
        while(dir && left <=right){
            mid = (left + right)>>>1
            dir = Math.sign(nums[mid]-target)
            &mid[dir]=mid - dir
         }
         return [dir, mid]
    }

for js sintax we need use q={'-1':0,1:nums.length-1} where left name for q[-1], mid for q[0] and right for q[1] or for q for all 3 is q[dir]

or the same for array indexing from 0:

we can use p=[0,,nums.length-1] where left is nikname for p[0], mid for p[1] and right for p[2] which is for all 3 of them is p[1+dir]

. :)

Answer 8

Assuming the array is sorted, here is a Pythonic answer with O(log n) runtime complexity:

def binary_search(nums: List[int], target: int) -> int:
    n = len(nums) - 1
    left = 0
    right = n
    
    
    while left <= right:
        mid = left + (right - left) // 2
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            right = mid - 1
        else:
            left = mid + 1
        
    
    return -1