Binary Search in Array

Question

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

Chico

Check this link – Finn

makes perfect sense to me. besides an array you could use a binary tree. – Dav

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
}

Bandage

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

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

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. – Offshoot

@NiklasR Except when low+high produces integer overflow. – Education

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

@Faitour 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 – Succentor

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

Acrobat

Answer 3

Implementing a binary search using just an array

Binary search is an optimized solution for searching an element in an array as it reduces search time by following three ways

• Either the element to be searched can be the middle element.
• If not middle then would be less than middle
• If both cases are not true would be greater than middle

If any of the above cases is not satisfied then such element is not present in an array.

Benefits of binary search

• One donot need to search the whole array. Either search to the middle or less than middle or greater than middle. Saves time of search.

Algorithm Steps

• Step 1: Calculate the mid index using the floor of lowest index and highest index in an array.

• Step 2: Compare the element to be searched with the element present at the middle index

• Step 3: If step 2 is not satisfied, then check for all element to the left of middle element. To do so equate high index = mid index - 1

• Step 4: If step 3 is not satisfied, then check for all elements to the right of the middle element. To do so equate low index = mid index + 1

if no case is satisfied then return -1 which means that element to be searched is not present in the whole array.

Code

# iterative approach of binary search
def binary_search(array, element_to_search):
    n = len(array)
    low = 0
    high = n - 1
    while low <= high:
        mid = (low + high) // 2
        if element_to_search == array[mid]:
            return mid
        elif element_to_search < array[mid]:
            high = mid - 1
        elif element_to_search > array[mid]:
            low = mid + 1

    return -1


array = [1, 3, 5, 7]
element_to_search = 8
print(binary_search(array=array,
                    element_to_search=element_to_search))

Recursive code can also be written for the binary search. Both (iterative and recursive) take O(logn) as the time complexity but when space complexity is to be considered then iterative approach for this solution will win as it takes O(1) whereas for recursive algo, three functions calls will be used in the function call stack and hence space complexity becomes equal to O(logn). Below is the recursive solution.

def recurs_binary_search(arr, element, low, high):
  if low > high:
    return -1
  mid  = (low + high) // 2
  if arr[mid] == element:
    return mid
  elif arr[mid] > element:
    return recurs_binary_search(arr,element, low, mid - 1) 
  else:
    return recurs_binary_search(arr,element, mid + 1, high)


array = [1, 3, 5, 7]
element_to_search = 7
low = 0
high = len(array) - 1
print(recurs_binary_search(arr=array, element=element_to_search,
low=low, high=high))

Yoong

Answer 4

Implementing Binary Search Algorithm in Java

pseudo-code flow for the Binary Search algorithm:

---

1. Set the start index (low) to 0 and the end index (high) to the length of the array minus 1.

2. While the start index is less than or equal to the end index:

• a. Calculate the middle index as the average of the start and end indices: mid = (low + high) / 2.
• b. Compare the middle element with the target value:
  • If they are equal, return the index of the middle element.
  • If the middle element is greater than the target value, update the end index to mid - 1.
  • If the middle element is less than the target value, update the start index to mid + 1.

3. If the target value is not found, return a value indicating that it is not present in the array.

---

The Iterative Approach

public int binarySearch(int[] arr, int size, int key){

        int startIndex = 0;
        int endIndex = arr.length - 1;

        int midIndex = startIndex + (endIndex-startIndex)/2 ;

        while (startIndex <= endIndex){
            if(key == arr[midIndex]) {
                return midIndex;
            }else if (key > arr[midIndex]){
                startIndex = midIndex + 1;
            }else {
                endIndex = midIndex -1;
            }

            midIndex = startIndex + (endIndex-startIndex)/2 ;
        }

        return -1; // Target element not found
    }

The Recursive Approach

public int binarySearchByRecursion(int[] arr, int key, int startIndex, int endIndex){
        if(startIndex > endIndex){
            return -1;
        }

        int midIndex = startIndex + (endIndex - startIndex) / 2;

        if(key == arr[midIndex]) {
            return midIndex;
        }else if (key > arr[midIndex]){
            return binarySearchByRecursion( arr,  key, midIndex + 1, endIndex);
        }else {
           return binarySearchByRecursion(arr, key, startIndex, midIndex -1);
        }

    }

Discover Comprehensive Solution Here https://github.com/Amir36036/ds/blob/array/src/main/java/org/ds/array/BinarySearch.java

Commotion

Answer 5

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

Appliance

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

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

@Education 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. – Appliance

Answer 6

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.

Axon

Answer 7

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

Secunderabad

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);/ – Keratin

Answer 8

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

Carmarthenshire

Answer 9

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]

. :)

Keratin

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. – Nicholle

Answer 10

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

Groark

Answer 11

Note that the array neeed to be sorted!

I think this is a simple one, using just value to look for and the array.

Recursive:

def bin_search(value, arr):
    
    hlf = len(arr)//2
    if len(arr) > 1:
        if value == arr[hlf]:
            return True
        elif value < arr[hlf]:
             return bin_search(value,arr[0:hlf])
        elif value > arr[hlf]:
             return bin_search(value,arr[hlf:])
    if len(arr) == 1:
        return value == arr[hlf]

Iterative:

def bin_search_iter(arr,value):

    found = False

    for i in range(arr[0],arr[len(arr)//2]):
        
        found = value == arr[0] or value == arr[len(arr)//2]
        
        if found or len(arr) == 1:
            break

        elif value > arr[len(arr)//2]:
            arr = arr[len(arr)//2:]
            print(">",arr)
            
        elif value < arr[len(arr)//2]:
            arr = arr[:len(arr)//2]
            print("<",arr)
            
    return found

all easy to read, no high and low indexes and log of n because it halves the array every time

Nineteenth