java - Binary search condition -

-

i'm confused condition of binary search algorithm , costs me lot of time in programming contests. question when use each of these conditions?
1. while (low < high)
2. while (high - low > 1)
3. while (low <= high)
low = lowest value in set of solutions.
high = largest value in set of solutions.

  1. while (low < high) used when you're searching range [low, high). when updating high, use high = mid. when updating low, use low = mid + 1.
  2. while (high - low > 1) used when you're searching range (low, high). when updating high, use high = mid. when updating low, use low = mid.
  3. while (low <= high) used when you're searching range [low, high]. when updating high, use high = mid - 1. when updating low, use low = mid + 1.

code below:

public class binarysearch {     public static void main(string[] args) {         integer[] nums = { 4, 9, 12, 18, 20, 26, 28, 29, 55 };          (int = 0; < nums.length; ++i) {             system.out.println(binarysearch1(nums, nums[i]));             system.out.println(binarysearch2(nums, nums[i]));             system.out.println(binarysearch3(nums, nums[i]));         }     }      public static <t extends comparable<t>> int binarysearch1(t[] array, t value) {         final int not_found = -1;         int low = 0;         int high = array.length;          while (low < high) {             int mid = low + (high - low) / 2;             int comparison = array[mid].compareto(value);              if (comparison == 0) {                 return mid;             } else if (comparison > 0) {                 high = mid;             } else {                 low = mid + 1;             }         }          return not_found;     }      public static <t extends comparable<t>> int binarysearch2(t[] array, t value) {         final int not_found = -1;         int low = -1;         int high = array.length;          while (high - low > 1) {             int mid = low + (high - low) / 2;             int comparison = array[mid].compareto(value);              if (comparison == 0) {                 return mid;             } else if (comparison > 0) {                 high = mid;             } else {                 low = mid;             }         }          return not_found;     }      public static <t extends comparable<t>> int binarysearch3(t[] array, t value) {         final int not_found = -1;         int low = 0;         int high = array.length - 1;          while (low <= high) {             int mid = low + (high - low) / 2;             int comparison = array[mid].compareto(value);              if (comparison == 0) {                 return mid;             } else if (comparison > 0) {                 high = mid - 1;             } else {                 low = mid + 1;             }         }          return not_found;     } }

Comments

Post a Comment

Popular posts from this blog

python - How to create jsonb index using GIN on SQLAlchemy? -

-
here's current code creating index jsonb. index("mytable_data_idx_id_key", mytable.data['id'].astext, postgresql_using='gin') but got error. sqlalchemy.exc.programmingerror: (psycopg2.programmingerror) data type text has no default operator class access method "gin" hint: must specify operator class index or define default operator class data type. [sql: "create index event_data_idx_id_key on event using gin ((data ->> 'id'))"] is there way create index on sqlalchemy? the postgresql specific sqlalchemy docs @ http://docs.sqlalchemy.org/en/latest/dialects/postgresql.html#operator-classes mention postgresql_ops dictionary provide "operator class" used postgresql, , provide example illustrating use: index('my_index', my_table.c.id, my_table.c.data, postgresql_ops={ 'data': 'text_pattern_ops', ...
Read more

PHP DOM loadHTML() method unusual warning -

-
i had following code works fine on localhost: $document = new domdocument(); $document->loadhtml($p_result); $form = $document->getelementsbytagname('form')->item(0); // code continues using $form variable after same code updated on outside server, loadhtml() failed , issued warning. warning: domdocument::loadhtml() expects parameter 1 valid path, string given in path/name/to/script.php returned null instead of object code pretty gets fatal error. note contents of $p_result absolutely same on outside server , on localhost. but why displays kind of warning , why not work? doesn't loadhtml() expects argument 1 string in first place? why method expects parameter 1 valid path ? just make clear i'm not calling loadhtmlfile() , i'm calling loadhtml() . thanks. you're affected one of php bugs . issue present in php 5.6.8 , 5.6.9. have affected php version on server, , bug-free version on localhost. the bug forbids null ...
Read more

c# - TransactionScope not rolling back although no complete() is called -

-
i'm using transactionscope rollback transaction fail bool errorreported = false; action<importerrorlog> newerrorcallback = e => { errorreported = true; errorcallback(e); }; using (var transaction = new transactionscope()) { foreach (importtaskdefinition task in taskdefinition) { loader.load(streamfile, newerrorcallback, task.destinationtable, processingtaskid); } if (!errorreported) transaction.complete(); } i'm sure there no transactionscope started ahead or after code. i'm using entity framework insert in db. regardless state of errorreported transaction never rolled in case of error. what missing ? transactionscope sets transaction.current . that's does. wants transacted must @ property. i believe ef each time connection opened reason. probably, connection open when scope installed. open connection inside of scope or enlist manually. ef has nasty "design decision": default opens ...
Read more